[백준] 2573 빙산 (파이썬 python)

 

 

문제 링크

 

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

2573번: 빙산

 

 

 

문제 풀이

 

def bfs(x, y):
    q = deque()
    q.append([x, y])
    visited[x][y] = 1
    while q:
        x, y = q.popleft()
        for dir in range(4):
            nx, ny = x + dx[dir], y + dy[dir]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                # 빙산일 경우
                if graph[nx][ny] > 0:
                    visited[nx][ny] = 1
                    q.append([nx, ny])
                # 물일 경우
                else:
                    water[x][y] += 1
    return 1

 

BFS를 통해 이어진 빙산들에 대해 모두 탐색을 해줍니다.

사분탐색을 했을 때 옆에 있는 것이 빙산일 경우 Queue에 넣어주고

물일 경우 water 배열의 탐색을 시작한 지점의 값을 1 늘려줍니다.

water 배열의 값은 bfs 탐색이 끝난 후 기존 배열에서 -를 해주어

해당 해에 녹은 높이를 줄여줄 것입니다.

 

while True:
    num = 0 # 이어진 빙산의 개수
    visited = [[0] * m for _ in range(n)]
    water = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if graph[i][j] > 0 and not visited[i][j]:
                num += bfs(i, j)
    for i in range(n):
        for j in range(m):
            graph[i][j] -= water[i][j]
            if graph[i][j] < 0:
                graph[i][j] = 0
    if num == 0 or num >= 2:
        break

    year += 1

 

 

빙산이 모두 사라지거나 분리될 때까지 while문을 돌리며

연도를 늘려가며 빙산을 녹입니다.

첫 번째 for문에서 빙산의 위치를 찾아 bfs를 돌려

해당 빙산과 이어진 빙산들을 모두 체크해주고 빙산 덩어리의 개수를 +1 갱신해줍니다.

방문처리가 되지 않은 빙산이 또 존재할 경우 해당 빙산에 대해서도 bfs를 돌려

빙산 덩어리의 개수를 +1 갱신시켜줍니다.

두 번째 for문에서는 빙산 주변의 물 만큼 빙산의 높이를 줄여줍니다.

이때, 빙산의 높이는 0보다 작아질 수 없으므로 작아질 경우 0으로 초기화시켜줍니다.

만약 빙산 덩어리가 존재하지 않거나, 분리되어 2개 이상일 경우 while문을 종료합니다.

그렇지 않을 경우 시간을 1 추가해주며 다음 반복을 진행합니다.

 

빙산 덩어리 수가 0일 경우 문제에서 제시한 대로 0을,

분리되었을 경우 시간(year)을 출력해주면 됩니다.

 

 

전체 코드

from collections import deque

def bfs(x, y):
    q = deque()
    q.append([x, y])
    visited[x][y] = 1
    while q:
        x, y = q.popleft()
        for dir in range(4):
            nx, ny = x + dx[dir], y + dy[dir]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                # 빙산일 경우
                if graph[nx][ny] > 0:
                    visited[nx][ny] = 1
                    q.append([nx, ny])
                # 물일 경우
                else:
                    water[x][y] += 1
    return 1


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]
year = 0

while True:
    num = 0 # 이어진 빙산의 개수
    visited = [[0] * m for _ in range(n)]
    water = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if graph[i][j] > 0 and not visited[i][j]:
                num += bfs(i, j)
    for i in range(n):
        for j in range(m):
            graph[i][j] -= water[i][j]
            if graph[i][j] < 0:
                graph[i][j] = 0
    if num == 0 or num >= 2:
        break

    year += 1

print(year) if num >= 2 else print(0)