23.03.09 파이썬 코딩 퀴즈#192 가장 먼 노드(프로그래머스 스쿨)

이번 문제는 가장 먼 노드 문제이다.

각각의 노드가 연결되어 vertex로 전달될때, 1번 노드 기준으로 가장 먼곳에 위치한 노드가 몇 개 인지를 return 해야 한다.

 

이번 문제는 DFS 가 아닌 BFS 이다. 깊이 탐색으로 풀어도 문제는 없어 보이지만, 이번 선택은 너비 탐색으로 정하였다.

먼저 전달받은 edge 를 노드 번호에 따라 연결된 노드에 저장할 nodes 를 만들었다.

즉 nodes[1] 에는 1번 노드와 연결된 노드 정보들이 [노드 번호, 거리] 형태로 추가가 된다.

그리고 각 거리마다 노드 정보를 저장할 distance 리스트를 미리 만들어 두었다.

이제 bfs() 함수를 [1,0]을 시작으로 돌게 된다.

먼저 전달받은 node[0]을 방문처리 해준다. (node[1] 은 거리이다)

그리고 이를 que 에 저장하고 반복문을 돌게된다.

다시 node를 v 라는 이름으로 꺼낸뒤, nodes[v[0]] (즉 nodes의 v[0] 번째에 연결된 노드들) 을 확인하게 되는데, 만약 방문한 적이 없는 노드라면 이를 que에 다시 넣어주게 되는데, 반드시 nod[1] 값을 현재 노드까지 기록된 거리만큼 증가시켜 주어야 한다. 

위 예시를 다시 예를 들면,

이런 형태의 노드 배치가 되는데, 1번 노드의 정보는 [1,0] 이다. 그리고 각 노드들은 [노드번호, 1] 로 저장된 상태이다.

따라서 1번 노드 기준으로 2번, 3번 노드들을 돌게 되는데, 이때 값의 변화는 없다.

다시 2번 노드를 기준으로 탐색을 하게 되고, 이때 5번 4번을 탐색하게 되고, 거리는 2번 노드의 거리값인 1이 증가된 2가 전달된다. 3번 노드를 탐색할때에는 4번은 이미 방문처리되었기 때문에 6번 노드의 값만 2로 증가된다.

따라서 이 거리값을 index 로 사용하여 distance에 저장하게 되면, distnace 배열안에 값이 존재하는 마지막 배열이 가장 거리가 긴 노드들이 된다.