[99클럽 코테 스터디 5일차 TIL] 알고리즘 수업 - 너비 우선 탐색 1 - 백준 24444

어제는 DFS라서 혹시나 했더니 역시나 오늘은 BFS다.

 

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

오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다.
아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다.
정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다.
정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.
너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.

bfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    for each v ∈ V - {R}
        visited[v] <- NO;
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    enqueue(Q, R);  # 큐 맨 뒤에 시작 정점 R을 추가한다.
    while (Q ≠ ∅) {
        u <- dequeue(Q);  # 큐 맨 앞쪽의 요소를 삭제한다.
        for each v ∈ E(u)  # E(u) : 정점 u의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
            if (visited[v] = NO) then {
                visited[v] <- YES;  # 정점 v를 방문 했다고 표시한다.
                enqueue(Q, v);  # 큐 맨 뒤에 정점 v를 추가한다.
            }
    }
}

[입력]
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000),
간선의 수 M (1 ≤ M ≤ 200,000),
시작 정점 R (1 ≤ R ≤ N)이 주어진다.
다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다.
(1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

풀이접근

이번에도 수도코드를 줬다.

때문에 수도코드 흐름대로 코드를 작성하면서 정점 방문 순서를 기록했다.

// 입력받기
let nmr = readLine()!.split(separator: " ").map{ Int("\($0)")! }
var graph: [[Int]] = Array(repeating: [], count: nmr[0]+1)
for _ in 0..<nmr[1] {
    let line = readLine()!.split(separator: " ").map{ Int("\($0)")! }
    graph[line[0]].append(line[1])
    graph[line[1]].append(line[0])
}

DFS에서 Stack을 사용했다면, BFS에서는 Queue를 사용하게 된다.

Swift에는 Queue 자료구조가 따로 없어 배열와 포인터 변수를 사용해서 구현사용한다.

var q: [Int] = []
var qp: Int = 0
var visited: [Int] = Array(repeating: 0, count: nmr[0]+1)
var index = 2

BFS 코드를 작성하고, 결과를 출력한다.

func bfs(_ start: Int) {
    q.append(start)
    visited[start] = 1
    while qp < q.count {
        let point = q[qp]
        qp += 1
        for i in graph[point].sorted() {
            if visited[i] == 0 {
                visited[i] = index
                index += 1
                q.append(i)
            }
        }
    }
}
bfs(nmr[2])
(1..<visited.count).forEach {
    print(visited[$0])
}

최종 코드 - Swift

let nmr = readLine()!.split(separator: " ").map{ Int("\($0)")! }
var graph: [[Int]] = Array(repeating: [], count: nmr[0]+1)
for _ in 0..<nmr[1] {
    let line = readLine()!.split(separator: " ").map{ Int("\($0)")! }
    graph[line[0]].append(line[1])
    graph[line[1]].append(line[0])
}
var q: [Int] = []
var qp: Int = 0
var visited: [Int] = Array(repeating: 0, count: nmr[0]+1)
var index = 2
func bfs(_ start: Int) {
    q.append(start)
    visited[start] = 1
    while qp < q.count {
        let point = q[qp]
        qp += 1
        for i in graph[point].sorted() {
            if visited[i] == 0 {
                visited[i] = index
                index += 1
                q.append(i)
            }
        }
    }
}
bfs(nmr[2])
(1..<visited.count).forEach {
    print(visited[$0])
}

최종 코드 - Python3

Python에는 Queue 구조를 지원한다!

역시 편하다.

import sys
import queue
input = sys.stdin.read
data = input().split()

index = 3
n,m,r = map(int, data[:index])
graph = [[] for _ in range(n+1)]
for _ in range(m):
  s, e = map(int, data[index:index+2])
  graph[s].append(e)
  graph[e].append(s)
  index += 2

q = queue.Queue()
visited = [0 for _ in range(n+1)]

def bfs(graph, visited, start):
  q.put(start)
  visited[start] = 1
  index = 2
  while q.qsize() > 0:
    point = q.get()
    for i in sorted(graph[point]):
      if visited[i] == 0:
        visited[i] = index
        index += 1
        q.put(i)

bfs(graph, visited, r)
print("\n".join(map(str, visited[1:])))

Conclusion

DFS만큼 BFS도 중요하다.

아주아주 기본적인 문제인 경우 잘 활용할 수 있지만 난이도가 조금이라도 올라가면 아직 풀기 어렵다.

 

+ 알에 금이 가기 시작했다!