Problem (23/09/03)

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

조건

• 빙산이 2개 이상으로 분리된 경우 소요된 시간 출력
• 빙산이 모두 녹아서 없어진 경우에는 분리될 수 없으므로 0 출력

Python Code

from sys import stdin
from collections import deque, defaultdict

N, M = map(int, stdin.readline().split())
mat = [list(map(int, stdin.readline().split())) for _ in range(N)]

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

def bfs(x, y):
	q = deque([(x, y)])
	info = defaultdict(int)
	while q:
		x, y = q.popleft()
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if 0 <= nx < N and 0 <= ny < M:
				if not mat[nx][ny]:
					info[(x, y)] += 1
				elif not visited[nx][ny]:
					q.append((nx, ny))
					visited[nx][ny] = 1
	for x, y in info:
		mat[x][y] -= info[(x, y)]
		if mat[x][y] < 0:
			mat[x][y] = 0 

year = 0
cnt = 0
while cnt < 2:
	cnt = 0
	year += 1
	visited = [[0] * M for _ in range(N)]
	for i in range(N):
		for j in range(M):
			if mat[i][j] and not visited[i][j]:
				cnt += 1
				visited[i][j] = 1
				bfs(i, j)
	if cnt == 0:
		year = 1
		break

print(year - 1)

Solution

• BFS를 이용해 풀이했다.

1. mat를 탐색하면서 얼음을 만나면 해당 얼음부터 bfs 탐색을 시작한다.
2. 현재 얼음의 상하좌우를 탐색한다.
   • 바다인 경우에는 dictionary에 키가 (x, y)일 때 값을 1 증가 시킨다.
   • 얼음인 경우에는 다음에 탐색하기 위해서 deque에 얼음 좌표를 추가한다.
3. deque에 남아있는 좌표가 없을 때까지 2로 돌아가 반복한다.
4. 현재 빙산을 다 탐색했다면 info에 저장된 값을 이용해 1년 동안 얼음이 녹은 값을 계산한다.
5. 빙산이 2개 이상으로 분리되거나 빙산이 모두 녹을 때까지 1로 돌아가 반복한다.

• 주변이 바다인 경우에 바로 뺄셈 연산을 하지 않는 이유는 모든 얼음이 동시에 녹아야 하기 때문이다.