이분탐색을 활용한 알고리즘 문제풀이

오늘 푼 문제: 가장 먼 노드

입출력

• 입력: 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어집니다.
• 출력: 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return합니다.

예제 코드

import java.util.*;

class Solution {
    /**
     * 1. 인접행렬 만들기
     * 2. BFS를 활용하여 1번 노드에서 가장 멀리 갈 수 있는 노드 구하기
     * 4. 해당 레벨에서 더 이상 갈 수 있는 노드가 없을 경우 해당 레벨에서 방문한 노드를 return;
     */
    public int solution(int n, int[][] edge) {
        int[] ch = new int[n + 1]; // 모든 노드를 최단 경로로 가기 때문에 방문한 노드는 재방문 할 수 없다.
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= n; i++) list.add(new ArrayList<Integer>());
        for (int[] vertex : edge) {
            list.get(vertex[0]).add(vertex[1]);
            list.get(vertex[1]).add(vertex[0]);
        }
        int answer = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        ch[1] = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Integer cq = q.poll();
                for (Integer nv : list.get(cq)) {
                    // 방문하지 않은 노드에 대해서만 처리
                    if (ch[nv] == 0) {
                        q.offer(nv);
                        ch[nv] = 1;
                    }
                }
            }
            // 마지막 레벨인지에 대하여 확인하는 로직
            if (q.isEmpty()) answer = size;
        }
        return answer;
    }
}

• 인접리스트와 BFS를 활용하여 풀었습니다.
• 마지막 레벨까지 탐색을 진행한 후 마지막 레벨에서 방문한 노드의 개수를 return 했습니다.

회고

• 그래프 문제에 많이 익숙해진 것 같아서 뿌듯합니다.
• 이제 수학, DP, 이분탐색, 해시 등의 알고리즘에 더 시간을 쓰고자 합니다.