[백준 18405번] BFS : 너비 우선 탐색, 그래프 이론

이 문서는 전문적이지 않습니다.

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

18405번: 경쟁적 전염

입력 :
첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력 :
S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.

"단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다."

 

 

 

 

 

#1

 

해당 문제를 읽은 후 해결 방법으로 떠올린 알고리즘은 'BFS 너비 우선 탐색' 알고리즘이다.

 

너비 우선 탐색(Breadth-fist search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

 

 

 

위 알고리즘의 가장 큰 특징은 모든 레벨을 레벨 순으로 방문한다는 것이다.

이를 활용하여 문제의 '몇 초 후' 를 트리의 깊이로 생각하고 문제에 접근했다.

 

 

 

 

import sys
from collections import deque

# N : 시험관 크기 , K : 바이러스 종류
N , K = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N)] # 2차원 바이러스 그래프
q = [] # BFS를 위한 queue 세팅

for i in range(N):
    graph[i] = list(map(int, sys.stdin.readline().split()))
    for m in range(N):
        if graph[i][m] != 0: # 각 바이러스의 처음 위치를 큐에 넣는다
            q.append((graph[i][m],i,m)) # (바이러스 종류, x좌표, y좌표) 정렬을 위해 0번째 인덱스를 바이러스의 종류로 세팅
q.sort() # 바이러스 우선순위에 맞게 구별
q.append('count') # 몇 초 후를 구별하기 위한 분기점

# S : 초 , X : x좌표 , Y : y좌표
S, X, Y = map(int, sys.stdin.readline().split())

q = deque(q)

# 바이러스 전염 동선
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, +1]

while S:
    now = q.popleft() # 처음 정렬을 기준으로 우선순위에 따라 바이러스가 나온다.
    if now == 'count': # 만약 분기점 도달
        S -= 1 # 1초 지났다.
        q.append('count') # 다음 분기점을 설정한다.
        continue # 반복문을 다시 시작한다.
    else:
        for i in range(4):
            nx = now[1] + dx[i]
            ny = now[2] + dy[i]
            if 0 <= nx < N and 0 <= ny < N :
                if not graph[nx][ny]: # 해당 좌표가 아직 전염되지 않았다면,
                    graph[nx][ny] = now[0] # 해당 좌표에 바이러스를 옮긴다.
                    q.append((now[0],nx,ny)) # 다음 전염을 위해 큐에 정보를 넣어준다.

print(graph[X-1][Y-1]) # 문제에서 제시한 좌표의 바이러스를 읽는다. 그래프에 패딩을 시키지 않았다. 그래서 각 좌표에 -1 을 더한다.

 

 

 

queue를 이용한 너비 우선 탐색으로 문제를 풀어나가니 수월하게 해결됐다.

 

 

고민했던 부분은 1초가 지난 시점을 컴퓨터가 알 수 있게 하는 것이었다.

 

 

 

#2

 

 

이 문제를 해결하기 위해서 초반 큐 세팅에서 마지막에 'count' 라는 문자열 데이터를 집어넣었다.

즉, queue.popleft() 의 값이 'count' 가 된 시점은 "1초 동안"의 바이러스 전염이 끝났다는 뜻이다.

또한, 큐 자료구조에서 'count'의 뒤에는 이미 "다음 1초 동안"의 전염데이터가 쌓여있다는 뜻이다.

1초가 지났다는 것을 알 수 있으므로 해당 정보를 갱신하고, 'count'를 다시 넣어줌으로써  "다음 분기점"을 세팅했다.

 

이를 반복하여 제시된 시간만큼 바이러스 전염을 진행시킬 수 있었다.

 

 

날씨가 많이 추워졌습니다.

 

 

 

 

 

#3

 

사용되지 않는 변수가 있어서 지워봤다.

 

 

'큐' 자료구조와 '너비 우선 탐색' 에 대한 학습을 한 덕분에 위 문제가 잘 해결됐다.

첫 주차에는 정말 어려웠을 문제인데, 성장해나가는 것 같아 뿌듯하다.

처음에는 내가 뭘 공부해야 하는지, 무엇을 모르는지, 무엇을 아는지 몰랐다.

아직 잘 모르겠지만, 적어도 조금은 어제보다 나아갔다는 확신이 든다.

 

 

 

 

 

 

날이 많이 추워졌습니다.
다들 따듯한 옷을 꺼내시고,
얼죽아 분들은 꼭 장갑을 착용하시기 바랍니다.

 

 

 

 

 

 

오랜만에 긴 글 읽어주셔서 감사드립니다.

22.11.18