99클럽 코테 스터디 8일차 TIL: 그래프

문제

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

풀이

전형적인 그래프 문제이다.
문제에서는 촌수를 계산하고 머 어렵지 않게 써놨지만,
이 문제는 모든 간선의 비용이 1인 노드사이의 거리를 출력하라는 것과 동일하다.

DFS, BFS 두 알고리즘으로 쉽게 풀 수 있는 문제였다.

소스코드

	let n = Int(readLine()!)!
	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let a = input[0], b = input[1]
	let m = Int(readLine()!)!
	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)
	graph[b].append(a)
	}
	var queue = [(a, 0)]
	var index = 0
	var answer = -1
	while queue.count > index {
	let current = queue[index]
	let node = current.0
	let d = current.1
	visited[node] = true
	if node == b {
	answer = d
	break
	}
	for nextNode in graph[node] {
	if !visited[nextNode] {
	visited[nextNode] = true
	queue.append((nextNode, d + 1))
	}
	}
	index += 1
	}
	print(answer)

view raw 2644_촌수계산.swift hosted with ❤ by GitHub

후기

어렵지 않게 풀 수 있는 문제였다.
챌린저 문제를 풀었어야 하는데.. 여러번 시간이 없다는 핑계로 안풀고 있다.
내일이랑 모레도 바쁠텐데 꼭 풀어보려고 노력해야지.