99클럽 코테 스터디 10일차 TIL: 방향 그래프

벌써 10일차라니.. 시간 정말 빠르다.

문제

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

풀이

이 문제는 99클럽 코테 스터디 중에 등장한 적 없었던 방향 그래프 문제이다.
여태 무방향 그래프 문제만 나왔었는데, 이번엔 방향 그래프 문제가 나왔다.

사실 방향 그래프라고 해서 뭐 대단한 것은 없고
말 그대로 간선에 방향이 있는 것이다.

이 문제에서는 x노드에서 최단 거리가 k인 노드들을 찾는 문제이다.
최단 거리를 찾는 것이므로, BFS 알고리즘을 사용해서 풀 수 있었다.

간선의 비용이 동일할 때 최단거리임을 보장하기 때문이다.

소스코드

	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let n = input[0], m = input[1], k = input[2], x = input[3]
	var graph = [[Int]](repeating: [], count: n + 1)
	var visited = [Bool](repeating: false, 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)
	}
	var queue = [(x, 0)]
	var index = 0
	var result: [Int] = []
	while queue.count > index {
	let currentNode = queue[index].0
	let cost = queue[index].1
	visited[currentNode] = true
	if cost == k {
	result.append(currentNode)
	}
	for nextNode in graph[currentNode] {
	if !visited[nextNode] {
	visited[nextNode] = true
	queue.append((nextNode, cost + 1))
	}
	}
	index += 1
	}
	print(result.isEmpty ? -1 : result.sorted().map { String($0) }.joined(separator: "\n"))

view raw 18352_특정 거리의 도시 찾기.swift hosted with ❤ by GitHub

후기

BFS 알고리즘에 이해가 있다면 쉽게 풀 수 있는 문제였다.