[백준 / 파이썬] 2573 빙산

BFS 함수를 2개만들었다.

1. 1년마다 녹는걸 구현하는 BFS 

2. 그 후에 몇덩이로 나눠졌는지 확인하는 BFS를 구현했다.

 

까다로웠던 부분은 첫번째 BFS에서 바다인 부분은 방문처리를 하면 안된다는 부분이다.

왜냐면 빙산은 상하좌우 빙하의 개수에 의해 깎여나가는데 바다를 방문처리해서 들리지 않게 된다면 깎이는 부분이 적어지기 때문이다.

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

time = 0
def bfs(a, b):
    global time
    visited = [[0] * m for _ in range(n)]
    q = deque()
    q.append((a, b))
    visited[a][b] = 1
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0<=ny<n and 0<=nx<m and not visited[ny][nx]:
                #  바다인 경우
                if graph[ny][nx] == 0:
                    if graph[y][x] > 0:
                        graph[y][x] -= 1
                # 빙산인 경우
                elif graph[ny][nx] != 0:
                    # 빙산인 경우만 방문처리, 바다는 2개 이상의 빙산에게
                    # 영향을 끼칠 수 있으므로 방문처리하면 안됨.
                    visited[ny][nx] = 1
                    q.append((ny, nx))

    time += 1

def checkBFS(a, b, visited):

    q = deque()
    q.append((a, b))
    visited[a][b] = 1

    while q:
        y, x = q.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < n and 0 <= nx < m:
                if not visited[ny][nx] and graph[ny][nx] != 0:
                    visited[ny][nx] = 1
                    q.append((ny, nx))

# 두 덩이 이상 갈라졌는지 체크.
def check():
    checkCnt = 0
    visited = [[0] * m for _ in range(n)]

    for r in range(n):
        for c in range(m):
            if graph[r][c] != 0 and not visited[r][c]:
                checkBFS(r, c, visited)
                checkCnt += 1

    return checkCnt

for r in range(n):
    for c in range(m):
        if graph[r][c] != 0:
            bfs(r, c)
            if check() >= 2:  # 빙산 몇 덩이인지 확인.
                print(time)
                exit()

print(0)