[백준] 2573: 빙산

빙산

1. 반복문 돌면서 빙산에서 녹는 얼음의 개수를 빼준다.
   1-1. 빙산의 높이가 0보다 작으면 0으로 빼주는거 잊지말기
   1-2. 반복문 돌 때는 년(year)수를 한번 돌 때마다 증가시킨다.
2. 얼음이 녹은 상태에서는 bfs 돌면서 빙산의 개수가 2개 이상이면 반복문 멈춘다.
   2-1 이때 bfs 도는 방법은 빙산의 높이가 0보다 클 때 방문해주고 bfs 또 들어가서 끝까지 들어간다. 이 과정이 한번 끝나면 카운트 증가
3. 카운트가 2 이상이면 년도수를 출력하고 빙하의 높이가 모두 0이면 0을 출력하고 프로그램을 종료시킨다.

핵심코드: 빙하가 줄고 dfs를 돌렸는데 시간초과가 났다 .
빙하가 0보다 크면 거기서부터 bfs 돌리면 간단하게 풀린다.
신선한 방법!

# 카운트 증가 시점: 1을 찾았을 때
	for i in range(n):
		for j in range(m):
			if graph[i][j] > 0 and not visited[i][j]:
				cntIsland += 1
				visited[i][j] = True
				q = [[i, j]]
				while q:
					lst = q.pop()
					for k in range(4):
						nx = lst[0] + dx[k]
						ny = lst[1] + dy[k]
						if nx < 0 or ny < 0 or nx >= n or ny>= m:
							continue
						if graph[nx][ny] > 0 and not visited[nx][ny]:
							visited[nx][ny] = True
							q.append([nx, ny])

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
	graph.append(list(map(int, input().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
year = 0
compare = [[0]*m for _ in range(n)]
while True:
	year += 1
	removeCnt = [[0]*m for _ in range(n)]
	for x in range(n):
		for y in range(m):
			if graph[x][y] > 0:
				for i in range(4):
					nx = x + dx[i]
					ny = y + dy[i]
					if nx < 0 or ny < 0 or nx >= n or ny >= m:
						continue
					if graph[nx][ny] == 0:
						removeCnt[x][y] += 1

	for i in range(n):
		for j in range(m):
			if graph[i][j] > 0:
				graph[i][j] -= removeCnt[i][j]
				if graph[i][j] < 0:
					graph[i][j] = 0
	visited = [[False]*m for _ in range(n)]
	cntIsland = 0
	# 카운트 증가 시점: 1을 찾았을 때
	for i in range(n):
		for j in range(m):
			if graph[i][j] > 0 and not visited[i][j]:
				cntIsland += 1
				visited[i][j] = True
				q = [[i, j]]
				while q:
					lst = q.pop()
					for k in range(4):
						nx = lst[0] + dx[k]
						ny = lst[1] + dy[k]
						if nx < 0 or ny < 0 or nx >= n or ny>= m:
							continue
						if graph[nx][ny] > 0 and not visited[nx][ny]:
							visited[nx][ny] = True
							q.append([nx, ny])

	if cntIsland >= 2:
		break
	result = 0
	for i in range(n):
		for j in range(m):
			result += graph[i][j]
	if compare == graph:
		print(0)
		exit()

print(year)