[프로그래머스] 가장 먼 노드(Level 3)

📝문제 링크

프로그래머스 > 그래프 > 가장 먼 노드 문제보기

🔑문제 KeyPoint

최단거리로 주어진 노드를 탐색해야 하기 때문에, BFS 탐색을 이용했다.

1. 인접리스트로 방문해야 하는 노드 표현 : LinkedList<Integer>[] adj = new LinkedList[n+1];
2. 큐를 이용하여 다음 depth를 찾고 반복하여 마지막 depth에 node개수를 return

2번 과정에 있어서, 방문하지 않은 노드를 무조건 탐색하게 코딩하여,
2depth에서 3depth로 넘어가는 부분을 처리하는 부분에서 한참 고민했다.

        while(!q.isEmpty()){
            start= q.poll();
            cnt ++;
            
            // 방문해야 하는 노드를 iterator를 이용하여 탐색
            Iterator<Integer> it = adjList[start].listIterator();
            int z = 0;
            while(it.hasNext()){
                int w = it.next();
                
                // 방문 할 노드를 q에 담고
                // 다음 depth에 대한 종료조건을 고민...
                if(!visited[w]){
                    visited[w]=true;
                    q.add(w);
                    cnt++;
                }
            }

        }

결국 오늘도 구팀장님께 여쭤보며, 해결을 하였다.
while문 안에 큐의 사이즈만큼 for문을 돌리면 내가 하고자 했던 것을 해결할 수 있다...

코드를 보며 이해해보자.

💻문제 풀이

// 인접리스트로 접근
public int solution(int n, int[][] edge ){
    int answer = 0;
    boolean[] visited = new boolean[n+1];
    LinkedList<Integer>[] adj = new LinkedList[n+1];           // 인접리스트 생성

    for(int i=0;i<n+1;i++){
        adj[i] = new LinkedList<Integer>();
    }

    // 간선을 인접리스트로 표현
    for(int i=0;i<edge.length;i++){
        int start = edge[i][0]-1;       // 0번째 인덱스부터 맞춰주기 위한 작업
        int end = edge[i][1]-1;

        adj[start].add(end);
        adj[end].add(start);
    }

    Queue<Integer> q= new LinkedList<>();
    q.add(0);                           // 1번노드가 곧 0번째 인덱스 (1 depth)
    visited[0]=true;

    while(!q.isEmpty()){
        int size = q.size();
        for(int i=0;i<size;i++){
            int v = q.poll();
            // 연결된 간선을 모두 q에 담기 (2 depth)
            // v == 0, adj[v] = {1,2} 가 담겨 있다. (2 depth)
            for(int j=0;j<adj[v].size();j++){
                int node = adj[v].get(j);
                if(!visited[node]){
                    visited[node]=true;
                    q.add(node);
                }
            }
        }
        // 모든 방문이 끝난경우가 최종 depth라고 판단.
        answer = size;
    }
    return answer;
}

전체 소스보기(git)

[참고]

[프로그래머스] 가장 먼 노드(java)