[백준] 빙산

[백준] 빙산

---

풀이

문제의 조건은 다음과 같다.

1. 매년 빙산의 동서남북의 0의 개수에 따라 칸에 있는 빙산이 다음 년도에 녹는다는 것.

2. 빙산이 0 일 경우, year = 0으로 출력

3. 빙산이 두 덩이 이상일 경우, 그 때의 년도 수를 출력하는 것.

위와 같은 조건을 맞추기 위해서,
먼저 bfs를 이용해 빙산의 개수를 세었다. 빙산의 개수를 세면서 주변의 0의 개수를 따로 받아 다른 이차원 리스트에 넣었다.
그리고 빙산의 개수가 2개 이상이면, while문을 끝내도록 하고,
빙산의 개수가 0개라면, 다 녹았다는 의미이므로 조건에 따라, year=0으로 출력했다.
위 두 조건이 아니라면, 1년을 더해주고 현재 빙산 좌표와 bfs에서 저장한 이차원 리스트를 빼주어, 빙산을 녹였다.
그리고 while문을 다시 시작했다.

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
year, bing = 0, 0

def bfs(x, y, visit):
    q = [[x,y]]
    while q:
        x, y = q[0]
        q = q[1:]
        for i in range(4):
            mx = x + dx[i]
            my = y + dy[i]
            if 0<=mx<n and 0<=my<m:
                if graph[mx][my] == 0:
                    graph_2[x][y] += 1
                elif visit[mx][my] == False:
                    visit[mx][my] = True
                    q.append([mx, my])

def year_graph(graph, graph_2):
    for i in range(n):
        for j in range(m):
            graph[i][j] = graph[i][j] - graph_2[i][j]
            if graph[i][j] < 0:
                graph[i][j] = 0

while bing==0:
    visit = [[False] * m for _ in range(n)]
    graph_2 = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if graph[i][j] > 0 and visit[i][j] == False:
                visit[i][j] = True
                bfs(i, j, visit)
                bing += 1

    if bing >= 2:
        break
    elif bing == 0:  # 실수한 부분
        year = 0
        break
    else:
        year += 1
        year_graph(graph, graph_2)
        bing = 0
print(year)

---

실수 및 배운 점

• 가장 먼저 실수했던 점은, dfs를 이용해서 빙산의 개수를 구했던 점이다.
  계속 Recursion Error 가 떠서 이유를 찾아보니, 재귀 관련 에러였고 Python에서 정한 최대 깊이보다
  재귀의 깊이가 더 깊어졌을 때 생기는 에러다. BOJ에서는 n=1000일 때가 최대였다.
  여기서는 칸의 개수가 10,000 이기 때문에 에러가 생긴 것 같다.

• bfs로 바꿔서 했던 또 다른 실수는 빙산을 bfs돌리면서 같이 녹였던 점이다. 0의 개수를 확인하고 바로 녹인다면,
  다음 빙산 칸 수에서 이전 0의 개수를 확인할 때, 잘못 셀 수 밖에 없게 된다.

• 빙산이 0일 때, year 값을 0으로 만드는 것 또한, 조건을 제대로 확인하지 못해서 실수가 생겼다.