백준 - 2573번(구현, 그래프)

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

2573번: 빙산

import copy
import sys
from collections import deque

# 조건에 따라 빙산이 녹는 것을 구현 여기서 주의점은 얼음은 동시에 녹기 때문에
# 옆에 있는 빙산이 녹아서 0이 되더라도 당장은 영향을 받지 않는다.
def check(x,y):
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    cnt = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (nx >= 0 and nx < n) and (ny >=0 and ny < m):
            if arr[nx][ny] == '0':
                cnt = cnt + 1

    if int(arr[x][y]) - cnt <= 0:
        arr[x][y] = 0
        # 올해에 녹은 얼음을 구분하기 위해 정수형 0으로 값을 취한다.
    else:
        arr[x][y] = str(int(arr[x][y]) - cnt)

# 섬의 개수를 찾아 준다.
# 상하좌우 탐색을 하다가 더 이상 양의 정수가 없으면 그것이 하나의 섬이 된다.
def find(t_arr):
    p = deque([])
    cnt = 0
    for i in range(n):
        for j in range(m):
            if t_arr[i][j] != '0':
                p.append([i, j])
                t_arr[i][j] = '0'

                while p:
                    x, y = p.popleft()
                    dx = [1, -1, 0, 0]
                    dy = [0, 0, 1, -1]

                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if (nx >= 0 and nx < n) and (ny >= 0 and ny < m):
                            if t_arr[nx][ny] != '0':
                                t_arr[nx][ny] = '0'
                                p.append([nx,ny])
                cnt = cnt + 1
                if cnt == 2:
                    return cnt

    return 1

n,m = map(int,sys.stdin.readline().split())

arr = []

for _ in range(n):
    arr.append(list(map(str,sys.stdin.readline().split())))

q = deque([])

for i in range(n):
    for j in range(m):
        if arr[i][j] != '0':
            q.append([i,j])

ans = 0

while q:
    x,y = q.popleft()
    check(x,y)

    if len(q) == 0:
        #q의 길이가 0이 될 때마다 1년이 지난 것이다.
        for i in range(n):
            for j in range(m):
                if arr[i][j] == 0:
                    arr[i][j] = '0'
                    # 한 해가 지났으니깐 정수형 0을 문자 0 으로 바꿔준다.

        for i in range(n):
            for j in range(m):
                if arr[i][j] != '0':
                    q.append([i, j])

        ans = ans + 1
        x_arr = copy.deepcopy(arr)

        if find(x_arr) == 2:
            print(ans)
            exit(0)
print(0)

함정이 가득한 구현 문제다. 우선 빙산이 녹는 것을 신경 써야 한다.
얼음은 동시에 녹기 때문에 옆에 있는 빙산이 먼저 다 녹아서 0이 되더라도 현재 녹고 있는 빙산에 영향을 주지 않는다.
따라서 이를 구분하기 위해 1년 안에 녹은 빙산은 정수형 0으로 설정했다.

 

큐의 길이 q의 길이가 0이 되었다는 것은 1년 동안 빙산의 탐색을 모두 마쳤다는 것이다.
따라서 현재 정수형 0으로 되어 있는 빙산은 다음 해부터는 옆에 있는 빙산에 영향을 끼칠 수 있기 때문에 문자형 '0'으로 바꿔준다.

 

그리고 현재 섬이 생성되었는지 판단해야 한다.

이는 우리가 기존에 탐색을 마친 arr배열 망가뜨리지 않기 위해서 deepcopy를 사용해서 배열 복사해준다.

파이썬은 새로운 변수에 기존 리스트를 할당하면 포인터처럼 해당 변수는 기존 리스트의 주소만을 가리킨다.

따라서 built in 모듈인 copy 모듈의 deepcopy를 사용해서 배열을 복사해줘야 기존 배열을 손상시키지 않고 사용 가능하다.
find 함수를 호출해서 상하좌우 탐색을 하면서 하나의 빙산에서 출발해서 더 이상 인접한 빙산이 없으면 그것은 하나의 섬이 된다.

이때 탐색한 빙산들은 '0'으로 바꿔서 다시 탐색하는 일이 없도록 한다.

반복문을 통해 계속 탐색하다가 또 다른 빙산을 발견하게 되면 그것은 또 다른 섬이 된다.

이를 cnt변수에 섬의 개수를 저장하여 반환한다.

반환 값이 2보다 크면 ans를 출력하고 종료하고 그렇지 않을 경우 0을 출력하고 종료한다.

20분 만에 모든 코드를 작성했지만 계속 틀렸다고 나왔다. 어이없는 곳에서 실수를 했다.

find 함수 안에 i를 for문의 인자로 이미 쓰고 있는데 해당 for문 하위에 존재하는 while문 안에 for문 인자로 또 i를 쓰고 있던 것이다.

이를 k로 고치고 나니 정답처리를 받았다.

오늘의 교훈: 반복문을 사용할 땐 항상 변수명에 유의합시다.