[백준/파이썬] 2573번

📍백준 2573번 문제

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

코드

from collections import deque
import sys
input = sys.stdin.readline

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


def bfs(i, j):
    que = deque()
    que.append((i, j))
    visited[i][j] = True
    while que:
        x, y = que.popleft()
        temp = 0
        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 ice[nx][ny] == 0:
                    temp += 1
                else:
                    que.append((nx, ny))
                    visited[nx][ny] = True
        ice[x][y] -= temp
        if ice[x][y] < 0:
            ice[x][y] = 0
    return 1


n, m = map(int, input().split())
ice = []

for _ in range(n):
    ice.append(list(map(int, input().split())))
cnt = 0
while True:
    visited = [[False] * m for _ in range(n)]
    res = 0
    temp = 0
    for i in range(n):
        for j in range(m):
            if ice[i][j] != 0 and visited[i][j] == False:
                res += bfs(i, j)
            elif ice[i][j] == 0:
                temp += 1
    if temp == n*m:
        break
    if res >= 2:
        break
    cnt += 1

if temp == n * m:
    print(0)
else:
    print(cnt)

풀이

BFS를 이용해서 풀면 된다.

• 현재 위치를 기준으로 (0,-1),(0,1)(-1,0),(1,0)에 0이 있다면, temp에 1을 더해준다.
• for문이 끝난다면, 현재 위치에서 temp값을 빼준다.(0의 개수만큼 녹으므로)
  만약, temp값을 뺀 값이 0보다 작다면 0으로 설정해준다.
• 그래서 총 구역이 2개가 되거나, 모두 0이라면 while 문을 탈출한다.