문제 링크

문제 설명

input: 0과 1로 이루어진 그래프, 0:공기, 1: 얼음 as graph
output: 얼음이 다 녹는 최소 시간 as time
function: BFS

이 문제는 전형적인 그래프 탐색 문제이다. 최단 거리를 구하는 것이 아닌 완전 탐색이므로 DFS/BFS 아무거나 사용해도 되는데, 나는 조금 더 익숙한 BFS를 선택했다.

특이 사항이라면 외부 공기(0)가 얼음(1) 옆에 2개 이상 있을 시 얼음이 녹는다.(1 ➡️ 0)

그런데, 외부 공기도 0이고 내부 공기도 0인데 이를 어떻게 구분시킬 것인가가 관건이다.

설계

그래프 탐색을 0부터 시작할 것이냐, 1부터 시작할 것이냐가 매우 중요하다.

나는 이 문제를 이미 알고 있었기 때문에 괜찮았지만 처음 풀 때는 1(얼음)부터 탐색을 시작해서 상당히 고생했다. 백준의 치즈가 동일한 문제이다.

위에서 언급한 것처럼 1부터 탐색을 시작하면 외부 0(공기)과 내부 0을 구분하기가 힘들다.

0부터 탐색을 진행해야 자연스럽게 1이면 패스하므로 내부 0은 취급을 안 할 수 있다.

1

q = deque([(a,b)]) # x,y
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    visited = [[False]*M for _ in range(N)]
    visited[0][0] = True

BFS 기본 세팅을 한다.

2

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 and not visited[nx][ny]:
                if not graph[nx][ny]:
                    q.append((nx,ny))
                    visited[nx][ny] = True
                else:
                    graph[nx][ny] += 1
    eliminate()

상하좌우를 탐색하며 그래프가 0(공기)이면 탐색을 계속 진행하고 1(얼음)이면 +1(공기 터치)을 해준다.

그리고 eliminate 함수를 이용하여 2번 이상 공기 터치가 된 부분을 제거한다.

3

# C 표시 지우기
def eliminate():
    for i in range(N):
        for j in range(M):
            if graph[i][j] >= 3:
                graph[i][j] = 0
            elif graph[i][j] >= 2:
                graph[i][j] = 1
    return

4

time = 0
while check():
    bfs(0,0)
    time += 1
print(time)

얼음이 다 녹을 때까지 BFS로 녹인다.

5

def check():
    for i in range(N):
        if sum(graph[i]):
            return True
    return False

얼음 액화 검사

코드

"""
1.BFS
2.

graph --BFS-->time

"""

# C 표시 지우기
def eliminate():
    for i in range(N):
        for j in range(M):
            if graph[i][j] >= 3:
                graph[i][j] = 0
            elif graph[i][j] >= 2:
                graph[i][j] = 1
    return

def bfs(a,b):
    q = deque([(a,b)]) # x,y
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    visited = [[False]*M for _ in range(N)]
    visited[0][0] = True

    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 and not visited[nx][ny]:
                if not graph[nx][ny]:
                    q.append((nx,ny))
                    visited[nx][ny] = True
                else:
                    graph[nx][ny] += 1
    eliminate()
    return

def check():
    for i in range(N):
        if sum(graph[i]):
            return True
    return False


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

N,M = map(int,input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int,input().split())))

time = 0
while check():
    bfs(0,0)
    time += 1
print(time)