백준 24444 - 알고리즘 수업 - 너비 우선 탐색1

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

24444번: 알고리즘 수업 - 너비 우선 탐색 1

 

 

 

 

 

 

 

 

이 문제는 트리 자료구조의 BFS 알고리즘의 대표적인 기초 문제라고 볼 수 있다.

 

이 문제를 해결하기 위해서는 다음과 같은 정보가 필요하다.

1. 각 노드들과 인접한 노드들의 정보 → 그래야 인접한 노드들을 타고 타고 들어갈 수 있다.

2. 각 노드들의 방문 여부 → 방문하지 않은 노드만 탐색하기 위함이다.

3. 인접 노드 방문을 시작하지 않은 노드의 정보 → 그래야 bfs 탐색이 가능함 

 

1번과 2번은 dfs 알고리즘에도 똑같이 적용되며, 3번은 bfs 알고리즘에서만 필요한 정보이고 이를 위해 deque를 사용했다.

 

1부터 N까지의 노드가 주어지기 때문에, 2차원의 리스트를 생성하여 i번 노드의 인접 노드들은 i번째 리스트에 담아 저장하도록 했다.

 

3번을 위해서는, 노드를 방문 처리한 후에도 해당 노드를 큐에 삽입해야 한다. 이미 방문했는데 왜 큐에 삽입하는 것일까? 해당 큐는 방문 할 노드를 저장하는 큐가 아니기 때문이다. 해당 큐는, 인접 노드 정보를 얻기 위해서 해당 노드를 저장하는 것이므로, 최종적으로는 큐에서 차례대로 노드를 꺼내어 해당 노드의 인접 노드 리스트를 가져와 탐색을 한다.

 

로직을 정리해보자.

시작 노드를 큐에 넣은 후, 시작 노드를 방문처리한다.

큐에 담겨 있는 노드가 없을 때까지 다음과 같은 반복문을 수행한다.

1. 큐의 맨 앞에 있는 노드를 꺼내어 해당 노드의 인접 노드 리스트를 확보하고 정렬

2. 정렬된 인접 노드를 하나씩 탐색. 특정 인접 노드의 방문 여부를 확인하고 방문하지 않았을 경우엔 방문 횟수를 증가시키고 방문 처리

3. 해당 인접 노드를 큐에 삽입(추후 해당 노드가 가지는 인접 노드를 방문하기 위해서이다.)

 

 

풀이 코드)

 

from collections import deque
import sys
sys.setrecursionlimit(10**6)  # 파이썬 기본 재귀 계산 깊이를 늘리기 위한 코드

def bfs(R):
    global cnt
    q = deque([R])  # 인접노드 정보를 꺼내기 위한 deque
    visited[R] = 1  # 시작 노드 방문 처리
    result[R] = cnt
    while q:
        now = q.popleft()  # 맨 앞에 있는 노드부터-
        graph[now].sort()  # 현재 노드와 인접한 노드 정보 정렬
        for node in graph[now]:  # 인접 노드 방문
            if visited[node] == 0:
                cnt += 1
                visited[node] = 1  # 방문 처리
                result[node] = cnt
                q.append(node)  # 인접노드 정보를 위해 해당 노드를 deque에 담기

N, M, R = list(map(int, sys.stdin.readline().split()))
graph = [[] for i in range(N+1)]  # 인접노드
visited = [0]*(N+1) # 방문 여부
result = [0]*(N+1)
for i in range(M):
    a, b = list(map(int, sys.stdin.readline().split()))
    graph[a].append(b)
    graph[b].append(a)

cnt = 1
bfs(R)

for i in range(1, N+1):
    print(result[i])

 

---

참고

https://heytech.tistory.com/56

https://takeu.tistory.com/242