(python) 그래프 순회 - 너비 우선 탐색(BFS) (Feat. 백준 2636)

1. 너비 우선 탐색(Breadth-First Search)

 

깊이 우선 탐색과 다르게 인접해 있는 노드를 우선적으로 탐색하는 알고리즘이다. 

 

즉, 현재 노드로부터 거리가 가까운 노드부터 차례로 방문한다.

 

BFS 예시

https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif

File:Breadth-First-Search-Algorithm.gif - Wikimedia Commons

 

위의 이미지는 너비우선탐색(BFS)의 예시를 보여준다.

 

2. 예제 적용 (백준 2636)

 

백준 2636

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

2636번: 치즈

 

문제 설명

 

외부 공간과 내부 공간을 분리하여 외부 공기와 맞닿는 부분의 치즈가 매시간마다 녹는다.

모든 치즈가 녹는 데 걸린 시간과 마지막까지 남아있는 치즈의 개수를 구하는 문제

 

문제 풀이

 

1. 치즈는 외부 공기에 반응하여 녹기 때문에 내부공기와 외부공기를 구분해야 한다. BFS를 이용하여 외부 공기와 인접한 지점들을 검사한다.

 

def divideExteriorAir():
    count_cheese = countingCheese() #현재 치즈 개수
    q = deque()
    q.append([0,0])     #0,0을 기준으로 시작
    input_list[0][0] = 2    #외부 공기는 2로 저장
    dir_x = [-1, 0, 0, 1]
    dir_y = [0, -1, 1, 0]
    while q:
        a, b = q.popleft()
        if input_list[a][b] == 2:
            for i in range(4):
                if 0 <= (a + dir_x[i]) < n and 0 <= (b + dir_y[i]) < m:
                    if input_list[a + dir_x[i]][b + dir_y[i]] == 0:
                        input_list[a + dir_x[i]][b + dir_y[i]] = 2  # 외부공기
                        q.append([a + dir_x[i], b + dir_y[i]])
    return count_cheese

 

2. 외부공기와 인접한 치즈를 녹인다. BFS를 이용하여 외부공기로부터 인접한 치즈 탐색한다.

 

def meltCheese():
    dir_x = [-1, 0, 0, 1]
    dir_y = [0, -1, 1, 0]
    for i in range(n):
        for j in range(m):
            if input_list[i][j] == 2:   #외부공기를 기준으로 탐색
                for k in range(4):
                    if 0 <= (i + dir_x[k]) < n and 0 <= (j + dir_y[k]) < m and input_list[i + dir_x[k]][j + dir_y[k]] == 1:
                        temp[i + dir_x[k]][j + dir_y[k]] = 2  # 치즈 녹아서 외부공기로 변환

 

3. 위의 두 과정을 치즈의 개수가 '0'이 될때까지 반복한다.

 

전체 코드

 

from copy import deepcopy
from collections import deque
def countingCheese():
    cnt = 0  # 현재 치즈 개수 확인
    for i in range(n):
        for j in range(m):
            if input_list[i][j] == 1:
                cnt += 1
    return cnt

def divideExteriorAir():
    count_cheese = countingCheese() #현재 치즈 개수
    q = deque()
    q.append([0,0])     #0,0을 기준으로 시작
    input_list[0][0] = 2    #외부 공기는 2로 저장
    dir_x = [-1, 0, 0, 1]
    dir_y = [0, -1, 1, 0]
    while q:
        a, b = q.popleft()
        if input_list[a][b] == 2:
            for i in range(4):
                if 0 <= (a + dir_x[i]) < n and 0 <= (b + dir_y[i]) < m:
                    if input_list[a + dir_x[i]][b + dir_y[i]] == 0:
                        input_list[a + dir_x[i]][b + dir_y[i]] = 2  # 외부공기
                        q.append([a + dir_x[i], b + dir_y[i]])
    return count_cheese

def meltCheese():
    dir_x = [-1, 0, 0, 1]
    dir_y = [0, -1, 1, 0]
    for i in range(n):
        for j in range(m):
            if input_list[i][j] == 2:   #외부공기를 기준으로 탐색
                for k in range(4):
                    if 0 <= (i + dir_x[k]) < n and 0 <= (j + dir_y[k]) < m and input_list[i + dir_x[k]][j + dir_y[k]] == 1:
                        temp[i + dir_x[k]][j + dir_y[k]] = 2  # 치즈 녹아서 외부공기로 변환
#입력 구간
n,m = map(int,input().split())
input_list = []
for i in range(n):
    input_list.append(list(map(int, input().split())))

t = 0   #총 소요 시간
res = []    #치즈 개수 저장 리스트

while True:
    res.append(divideExteriorAir())
    temp = deepcopy(input_list)
    meltCheese()
    input_list = deepcopy(temp) #초기 리스트 업데이트
    t += 1  #1시간 소요

    check = 1
    for i in range(n):
        for j in range(m):
            if input_list[i][j] == 1:
                check = 0
    if check == 1:  #치즈가 하나도 없을 경우 무한루프 종료
        break

    for i in range(n):
        for j in range(m):
            if input_list[i][j] != 1:
                input_list[i][j] = 0    #치즈를 제외한 부분 0으로 교체
#결과 출력
print(t)
print(res[len(res) - 1])