[코테/JAVA] 그래프: 가장 먼 노드

2022.02.06

82번째 포스팅

 

입사 336일차.

코테 문제풀이 12주차 1번 문제

 

 

0. 문제

  ① 그래프 : 가장 먼 노드

  ② 설명

문제설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

  ③ 링크

코딩테스트 연습 - 가장 먼 노드

 

 

1. 접근방법

  생각해낸 방법은 2가지

  ① bfs

  ② dfs

 

 

2. 풀이

  ① 접근방법 : ①

  ② 풀이

import java.util.*;
 
class Solution {
    public int solution(int n, int[][] edge) {
        int answer = bfs(n, edge);
        return answer;
    }
    
    public int bfs(int n, int[][] edge) {
        boolean[] flag = new boolean[n + 1];
        boolean[][] vertex = new boolean[n + 1][n + 1];
 
        // 1. 그래프이므로 양방향으로 이동할 수 있어야 한다.
        for (int[] nodeArr : edge) {
            vertex[nodeArr[0]][nodeArr[1]] = true;
            vertex[nodeArr[1]][nodeArr[0]] = true;
        }
        
        // 2. bfs는 Queue를 이용한다.
        Queue<Integer> queue = new LinkedList<>();
        
        
        // 3. 출발점의 위치를 queue에 넣어준다.
        queue.add(1);
        
        // 4. 한 번 거쳐간 위치는 통과여부를 체크해준다.
        flag[1] = true;
 
        
        int answer = 0;
        while (!queue.isEmpty()) {
            
            /* 
             * 5. 사이즈는 변수로 따로 저장한다.
             * 변수로 따로 저장하지 않으면, queue의 사이즈가 계속 변하므로 원하는 값을 가져올 수 없다.
             */
            int queueSizeTmp = queue.size();
            
            for (int i = 0; i < queueSizeTmp; i++) {
                
                // 6. 현재위치를 가져온다.
                int location = queue.poll();
                for (int j = 1; j < n + 1; j++) {
                    
                    // 7. 현재위치에서 갈 수 있는 장소와 이미 한 번 거쳐간 장소인지 여부를 체크한다.
                    if (vertex[location][j] && !flag[j]) {
                        flag[j] = true;
                        queue.add(j);
                    }
                }
            }
            
            /* 
             * 8. 가장 멀리 떨어진 노드는 가장 많은 장소를 거친 곳이다.
             * bfs는 최단거리를 찾아주기 때문에, 가장 먼 곳까지 걸리는 시간 혹은 간선의 수를 찾고싶다면,
             * queue의 사이즈가 가장 클 때를 찾아주면 된다.
             */
            answer = queueSizeTmp;
        }
 
        return answer;
    }
}

 

 

3. 결과

 

 

4. 주의사항

  ① 첫번째 반복문을 돌 때, queue의 사이즈를 queue.size()로 사용하지 않고, 따로 변수로 저장해야한다.