BFS - 빙산 [ 2573번 ]

2022. 7. 20. 13:452022/BaekJoon_알고리즘

from copy import deepcopy
from collections import deque

# 섬 개수 타운팅
def bfs(x, y):
    global visited
    visited[x][y] = True
    q = deque([(x, y)])
    while q:
        x, y =  q.popleft()
        chk = False
        for i in range(4):
            nx = x+dx[i]; ny = y+dy[i]
            if 0<=nx<N and 0<=ny<M and visited[nx][ny] == False:
                if graph[nx][ny] > 0:
                    chk = True
                    visited[nx][ny] = True
                    q.append((nx, ny))
                    
N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))
    
dx = [1, 0, -1, 0]; dy = [0, 1, 0, -1]
year = 0; island = 0
while True:
    if island >= 2:
        print(year)
        break
        
    chk = False
    copyGraph = deepcopy(graph)
    for i in range(N):
        for j in range(M):
            if graph[i][j] > 0:
                chk = True
                for k in range(4):
                    ni = i+dx[k]; nj = j+dy[k]
                    if 0<=ni<N and 0<=nj<M and graph[ni][nj] == 0:
                        if copyGraph[i][j]>0:
                            copyGraph[i][j] -= 1

    graph = copyGraph
                            
    # 빙하가 다 녹아 반으로 나뉘어질 수 없는 경우
    if chk == False:
        print(0)
        break
    
    visited = [[False] * M for _ in range(N)]
    island = 0
    for r in range(N):
        for c in range(M):
            if graph[r][c] != 0 and visited[r][c] == False:
                bfs(r, c)
                island+=1
    year+=1

'2022 > BaekJoon_알고리즘' 카테고리의 다른 글

BFS - 맥주 마시면서 걸어가기 [ 9205번 ]  (0) 2022.07.22
BFS - 토마토 [ 7569번 ]  (0) 2022.07.22
BFS - 스타트링크 [5014번]  (0) 2022.07.18
BFS - 안전영역  (0) 2022.07.18
DFS - 촌수계산 [2644번]  (0) 2022.07.17