99클럽 코테 스터디 22일차 TIL, 그래프(가장 먼 노드)

1. 문제 정의

2. 문제 접근

결국 모든 노드를 그래프 형태로 만들어서 bfs 돌면서 노드들을 탐색하며 노드사이의 길이를 갱신해주면 된다.

3. 문제 풀이

1. 그래프를 만든다.
2. BFS를 돌면서 모든 노드를 탐색하며 길이를 갱신해준다.
3. 최대 깊이의 정답을 리턴한다.

4. 코드

import java.util.*;

class Solution {
    static boolean[] visit;
    static List<Integer>[] list;
    static int answer;

    public int solution(int n, int[][] edge) {
        answer = 0;
        visit = new boolean[n + 1];
        list = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int[] e : edge) {
            list[e[0]].add(e[1]);
            list[e[1]].add(e[0]);
        }
        bfs();

        return answer;
    }
    private static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{1, 0}); //[nodeNum,distance]
        visit[1] = true;
        int maxDepth = 0;

        while (!q.isEmpty()) {
            int[] temp = q.poll();
            int now = temp[0];
            int depth = temp[1];

            if (maxDepth == depth) {
                answer++; // 최대 거리와 같을 경우
            } else if (maxDepth < depth) { //현재 노드의 길이가 더 길다면 값 갱신
                answer = 1;
                maxDepth = depth;
            }

            for (int next : list[now]) {
                if (!visit[next]) {
                    q.add(new int[]{next, depth + 1});
                    visit[next] = true;
                }
            }

        }
    }
}

 

 

5. 회고

그래프 문제에서 노드를 돌며 최단거리를 많이 물어보는 것 같다. 언뜻 BFS문제랑 비슷해 보이면서 다르다. 노드를 구성해서 어떻게 원하는 바를 구할지를 계속 생각해보자.