프로그래머스 '가장 먼 노드' 문제풀이 - Henry's Algorithm

 

 

 

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

nvertexreturn

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

 

 

 

문제 푸는 방법:

BFS 알고리즘으로 한 칸씩 가면서 Count를 +1 씩 해주면된다.

마지막 Visited 리스트에서 Counter 함수를 통해 중복값끼리 모으고 Sorting 하여 최대값을 알아낸다.

 

정답 코드:

from collections import deque, Counter

def solution(n, edge):
    answer = 0
    graph = {}
    for i in edge:
        if i[0] in graph:
            graph[i[0]].append(i[1])
        else:
            graph[i[0]] = [i[1]]
        if i[1] in graph:
            graph[i[1]].append(i[0])
        else:
            graph[i[1]] = [i[0]]
    
    result = bfs(graph,1)
    result = sorted(result.values(), reverse=True)
    return list(Counter(result).values())[0]

def bfs(edge,root):
    visited = {}
    queue=deque([[root,0]])
    arr = [[root,0]]
    while queue:
        current = queue.popleft()
        if current[0] not in visited:
            visited[current[0]] = current[1]
            add = set(edge[current[0]]) - set(visited)
            queue += ([[i,current[1]+1] for i in add])
    return visited

 

나의 생각:

드디어 경로 문제의 첫 발을 띄었다.

항상 알고리즘 문제에서 경로 문제를 제일 어려워했는데,

프로그래머스의 Level 2의 조금 쉬운 문제로 시작했다.

생각보다 어려운 공식이 아니었다. 앞으로 경로 문제 풀 때 괜히 겁먹지 말자!

화이팅!!

 

 

NHN 코딩테스트를 대비하며 Java 로도 풀어보았다.

푸는 방식은 위의 파이썬 코드 설명과 같다. 화이팅!

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<edge.length; i++){
            list.add(new ArrayList<Integer>());
        }
        for(int[] i:edge){
            int a = i[0];
            int b = i[1];
            list.get(a).add(b);
            list.get(b).add(a);
        }
        int[] cnt = new int[n+1];
        cnt[0]=cnt[1] = 0;
        boolean[] visited = new boolean[n+1];
        visited[0]=visited[1] = true;
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);// 시작점
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int v:list.get(cur)){
                if(!visited[v]){
                    visited[v] = true;
                    cnt[v] = cnt[cur]+1;
                    q.add(v);
                }
            }
        }
        int max = 0;
        int ans = 0;
        for(int i: cnt){
            if(max<i){
                max = i;
                ans = 1;
            }else if(max == i){
                ans += 1;
            } 
        }
        
        return ans;
    }
}