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로도 풀어봐야겠다고 생각해서 두 방법으로도 풀이해보았다.

소스코드

후기

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