[백준 20058번] 마법상어와 파이어스톰(파이썬)

https://www.acmicpc.net/problem/20058

20058번: 마법사 상어와 파이어스톰

문제가 요구하는 것이 상당히 많고

배열도 큰 편이라

차근차근 푸는 게 중요했습니다.

이 문제에서는 격자를 돌려주는 것과

인접한 얼음을 보고 뺴주는 것

2개를 구현하는 것이 관건이었습니다.

먼저, 격자로 돌려주는 걸 먼저 볼까요??

저는 컴퓨터에서

한줄 한줄씩 받고

돌려주는 경우를 생각했습니다.

L=2인 격자인 경우를 생각하면서

문제를 그려봤습니다.

이걸 구현하기 위해

tmp에 임시로 행렬을 받고

알맞은 돌림위치에 값을 넣어주었습니다.

그 다음은 얼음빼기인데

'이거 개쉽네.

리스트 지나갈 때 마다

인접한 거 판별하고

-1빼주면 개꽁이네.'

라고 생각하기 쉽습니다.

하지만 그렇게 구현하면

문제를 아예 틀리게 됩니다.

저렇게 그림처럼

NG의 케이스가 나오게 됩니다.

사람마다 풀이방법은 다양한데

저는 별도의 리스트를 만들어

얼음이 있는 리스트를복사했습니다.

그래서 얼음 각 요소를 돌면서

각 요소에 인접한 얼음을 판별하되

복사한 리스트의 얼음을 빼주었습니다.

이렇게하면

계속 얼음의 인접한 요소를 구하더라도

빼주기 전의 원래상태대로 판별할 수 있습니다.

끝난 뒤에는 원래 복사한 것을

얼음으로 다시 복사를 시켜주면서

빼주는 걸 완성했습니다.

코드를 보겠습니다.

 

# 백준 20058번 마법사 상어와 파이어스톰
from collections import deque
import copy

N, Q = map(int, input().split())
len_ices = 2 ** N
ices = [list(map(int, input().split())) for _ in range(len_ices)]
level = list(map(int, input().split()))
# 인접한거 판단
dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]
"""
magic=2


for r in range(0,len_ices,2**magic):

  for c in range(0,len_ices,2**magic):

    tmp=[[]for _ in range(2**magic)]
    i=0

    for tmp_r in range(r,r+2**magic):
      tmp[i]=ices[tmp_r][c:c+2**magic]
      i+=1
    print(tmp)
    j=0
    for tmp_c in range(c+2**magic-1,c-1,-1):
      print(tmp_c)
      print()
      k=0
      for tmp_r in range(r,r+2**magic):
        print(tmp_r)
        ices[tmp_r][tmp_c]=tmp[j][k]
        k+=1
      print()
      j+=1
print(ices)
sum_ice=0
for i in range(len_ices):
  for j in range(len_ices):
    sum_ice+=ices[i][j]
print(sum_ice)

"""
for magic in level:
    # 격자 만들어서 돌리기
    # 0이면 격자를 만들 것도 없으므로, 0보다 큰 경우만 생각.
    if magic > 0:
        for r in range(0, len_ices, 2 ** magic):
            for c in range(0, len_ices, 2 ** magic):

                tmp = [[] for _ in range(2 ** magic)]
                i = 0

                for tmp_r in range(r, r + 2 ** magic):
                    tmp[i] = ices[tmp_r][c:c + 2 ** magic]
                    i += 1
                j = 0
                for tmp_c in range(c + 2 ** magic - 1, c - 1, -1):
                    k = 0
                    for tmp_r in range(r, r + 2 ** magic):
                        ices[tmp_r][tmp_c] = tmp[j][k]
                        k += 1
                    j += 1
    # 돌린 후, 인접한 얼음 3이상 없으면 하나 빼줌.
    # 한번에 해야하므로, 임시저장 후 옮겨주는 걸로 해보자.
    # print(ices)
    tmp = copy.deepcopy(ices)
    # print(tmp)
    for r in range(len_ices):
        for c in range(len_ices):
            count = 0
            for d in range(4):
                nr = r + dr[d]
                nc = c + dc[d]
                if (nr < 0 or nr >= len_ices) or (nc < 0 or nc >= len_ices):
                    # count+=1
                    continue
                if ices[nr][nc]:
                    count += 1
            if count < 3:
                if tmp[r][c]:
                    tmp[r][c] -= 1
                # print("no")

    # print(ices)
    # print(tmp)
    ices = tmp
# print(ices)
# 남아있는 얼음의 합
sum_ice = 0
for i in range(len_ices):
    for j in range(len_ices):
        sum_ice += ices[i][j]

# 가장 큰 덩어리가 차지하는 칸의 갯수
max_ice = 0
# BFS로 구하자
visited = [[False] * len_ices for _ in range(len_ices)]
for r in range(len_ices):
    for c in range(len_ices):
        if ices[r][c] and visited[r][c] == False:
            q = deque()
            q.append((r, c))
            tmp = 0
            while q:
                r_p, c_p = q.popleft()
                for i in range(4):
                    nr = r_p + dr[i]
                    nc = c_p + dc[i]
                    if (nr < 0 or nr >= len_ices) or (nc < 0 or nc >= len_ices):
                        continue
                    if ices[nr][nc] and not visited[nr][nc]:
                        q.append((nr, nc))
                        visited[nr][nc] = True
                        tmp += 1
            max_ice = max(max_ice, tmp)

print(sum_ice)
print(max_ice)

  

문제의 길이가 길다보니

격자돌리는 것 같은 경우에는

밖에 임시적인 코드를 작성해서

코드 동작여부를 확인했습니다.

이 문제에서 주의해야할 점은

1. 얼음을 빼줄 때

얼음이 있는 케이스에만 빼준다

--->문제의 예제6를 돌리다보면

어?1 2 3 4 5까지는 맞는데

왜 6에서 나가지?

하는 경우가 발생할 수 있습니다.

그 이유는 0보다 클 떄

얼음이 있다고 문제에서 주어졌는데

0이거나 그 이하일 때도 빼주다보니

얼음에 음수가 입력이 되는 경우입니다.

2. 가장 큰 덩어리?

-->이 문제를 풀다가

처음에 가장 이해가 안갔던 부분이었습니다.

남아있는 얼음 중 가장 큰 덩어리?

얼음의 크기가 가장 큰 게 몇 개라는 건가?

하고 문제를 자세히 읽다가

이건 얼음이 이어진 크기구나 라는 걸 생각하고

바로 BFS를 활용했습니다.

3. 최대라도 해서

무지성으로 -1e9쓰지말자.

뭐의 최대인지 생각.

-->코드를 제출했더니

52%에서 틀렸다고 떴습니다.

대체 뭐에서 틀린거지 보다가

가장 큰 덩어리에서 초기값을

-1e9라고 두었습니다.

보통 최대 최소를 구할 때

처음 값을 1e9 -1e9라고 두고 풀어서

이것도 늘 풀듯이 그렇게 풀었습니다.

하지만 얼음의 값은 최소 0이기 때문에

나중에는 0으로 초기화를 하여 코드를 제출하였고

정답을 맞출 수 있었습니다.

 

오늘의 결론:

거의 다 풀어가는데

틀렸다고 뜰 경우

알고리즘정검하고

놓친 범위나 조건이 없는지

문제에서 다시 확인한다.