99클럽 코테 스터디 7일차 TIL: 트리

문제

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

풀이

접근방법

1. 이 문제에서 명확하게 "트리" 라고 알려주었다.
2. "트리"는 무뱡항 그래프이다.
3. DFS, BFS 등 트리를 구현해서 풀 수 있겠다고 생각했다.

DFS, BFS로 풀 때, 간선의 비용을 graph에 저장해두어야 겠다고 생각했다.
그래서 그래프의 자료형을 [[(Int, Int)]] 형식으로 튜플의 2차원 배열로 선언해주어야겠다고 생각했다.
물론 Struct나 Class, typealias 만들어줬어도 상관없다.

첫번째로 풀이했을 때는 DFS로 풀어보았다.
문제에서 간선의 개수는 노드의 개수 - 1 이고 같은 노드 번호는 주어지지 않으므로, 모든 노드가 연결되어있음을 알 수 있었다.

startNode에서 DFS를 수행했다. startNode에서 DFS를 수행하면서 endNode에 도달했다면 해당 노드까지의 비용을 출력해주었다.

BFS로도 풀어봐야겠다고 생각해서 두 방법으로도 풀이해보았다.

소스코드

	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let n = input[0], m = input[1]
	var graph = [[(node: Int, depth: Int)]](repeating: [], count: n + 1)
	for _ in 0..<n-1 {
	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let a = input[0], b = input[1], d = input[2]
	graph[a].append((b, d))
	graph[b].append((a, d))
	}
	func bfs(start: Int, end: Int) {
	var visited = [Bool](repeating: false, count: n + 1)
	visited[start] = true
	var queue = [(start, 0)]
	var index = 0
	while queue.count > index {
	let node = queue[index].0
	let cost = queue[index].1
	visited[node] = true
	if node == end {
	print(cost)
	break
	}
	for next in graph[node] {
	let nextNode = next.0
	let c = next.1
	if !visited[nextNode] {
	visited[nextNode] = true
	queue.append((nextNode, cost + c))
	}
	}
	index += 1
	}
	}
	for _ in 0..<m {
	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let start = input[0], end = input[1]
	bfs(start: start, end: end)
	}

view raw 1240_노드사이의 거리(BFS).swift hosted with ❤ by GitHub

	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let n = input[0], m = input[1]
	var graph = [[(node: Int, depth: Int)]](repeating: [], count: n + 1)
	for _ in 0..<n-1 {
	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let a = input[0], b = input[1], d = input[2]
	graph[a].append((b, d))
	graph[b].append((a, d))
	}
	var visited = [Bool](repeating: false, count: n + 1)
	func dfs(start: Int, end: Int, depth: Int) {
	visited[start] = true
	if start == end {
	print(depth)
	return
	}
	for next in graph[start] {
	let nextNode = next.node
	let depth = next.depth + depth
	if !visited[nextNode] {
	visited[nextNode] = true
	dfs(start: nextNode, end: end, depth: depth)
	}
	}
	}
	for _ in 0..<m {
	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let start = input[0], end = input[1]
	visited = [Bool](repeating: false, count: n + 1)
	dfs(start: start, end: end, depth: 0)
	}

view raw 1240_노드사이의 거리(DFS).swift hosted with ❤ by GitHub

후기

어렵지 않게 풀 수 있는 문제였다. 약 10분? 정도 걸린 것 같다