99클럽 코테 스터디 5일차 TIL: BFS

문제

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

풀이

문제 이름에서 나와있는대로 BFS를 구현하는 문제이다.
BFS는 많이 풀어봤던 문제이고 로직 또한 익숙했다.

문제에서 무방향 그래프로 나타나있어서, 인접행렬 혹은 인접리스트로 구현할 때 처리를 해주어야 했다.
추가로 오름차순 순으로 방문해야 하기 때문에, 정렬이 필요했다.

BFS는 Queue 자료구조를 사용하는데, Queue에 넣을 때 방문한 순서를 1증가시켜 주었다.
또한 visited 배열을 방문한 순서를 들고 있도록 하기 위해 Int 배열로 만들어주었다.
여기서 visited[i] = 0 이면 미방문 노드이고, 2라면 2번째 순서로 방문한 노드와 같이 생각하면 된다.

문제에서 방문하지 못하는 노드의 순서는 0으로 처리하라고 되어있어서 그 부분 처리도 가능하다.

일단 문제는 풀었다.
다만 문제에 나와있는 슈도코드 중에 이해가 잘 가지 않는 부분이 있었다.
for each v ∈ V - {R}

해당 부분은 visited 배열을 초기화 하는 부분인 것 같은데..

이해가 안가서 GPT한테 물어봤다..

아하 첫번째 노드를 제외하고 나머지 노드를 방문처리 해주는 코드였다.

소스코드

	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let n = input[0], m = input[1], r = input[2]
	var graph = [[Int]](repeating: [], count: n + 1)
	var visited = [Int](repeating: 0, count: n + 1)
	for _ in 0..<m {
	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let a = input[0], b = input[1]
	graph[a].append(b)
	graph[b].append(a)
	}
	for i in 1...n { graph[i] = graph[i].sorted(by: <) }
	var queue = [r]
	var index = 0
	var order = 1
	visited[r] = 1
	while queue.count > index {
	let currentNode = queue[index]
	for nextNode in graph[currentNode] {
	if visited[nextNode] == 0 {
	order += 1
	visited[nextNode] = order
	queue.append((nextNode))
	}
	}
	index += 1
	}
	print(visited[1...].map { String($0) }.joined(separator: "\n"))

view raw 24444_알고리즘 수업 - 너비 우선 탐색 1.swift hosted with ❤ by GitHub

후기

BFS를 사용하는 간단한 문제였다.