[BOJ] 백준 1240 노드사이의 거리 (Swift)

문제

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로도 풀어봐야겠다고 생각해서 두 방법으로도 풀이해보았다
BFS로 풀이할 때는 queue에 간선의 비용(cost)를 담아주는 방식으로 풀이했다.

 

소스코드

후기

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