[Programmers] Farthest Node

https://programmers.co.kr/learn/courses/30/lessons/49189

Solution

ref: Blog This is a graph traversal problem, so you can pick whichever of DFS or BFS you prefer. I went with BFS.

1. Since only edge relationships are given, build a new graph dictionary that stores adjacent nodes for each node.
2. Starting from node 1, run BFS on the graph dictionary.
3. It’s an undirected graph with no edge weights. So by updating distance values the first time each node is visited during BFS, we get the shortest distance from node 1.

Code

https://github.com/naem1023/codingTest/blob/master/graph/pg-49189.py