(코테) 프로그래머스_가장 먼 노드 *bfs 그래프

 

 

 

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

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

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

 

 

입출력 예
n vertex return
6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3

 

 

 

 

 

.

 

 

 

 

 

 

 

 

 

bfs 풀이 정석코드 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;

        List<List<Integer>> graph = new LinkedList<>();
        int[] data = new int[n + 1];

        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new LinkedList<>());
        }

        // 간선 양방향 연결
        for (int[] next : edge) {
            int first = next[0];
            int second = next[1];
            graph.get(first).add(second);
            graph.get(second).add(first);
        }

        data[1] = 0;  // 시작 노드
        int[] resultData =bfs(1, graph, data);

        // 가장 큰 거리 구하기
        int max = 0;
        for (int d : resultData) {
            max = Math.max(max, d);
        }

        // 가장 먼 노드 개수 세기
        int count = 0;
        for(int next:resultData){
            if(max==next) count++;
        } 

        return count;
    }

    public int[] bfs(int start, List<List<Integer>> graph, int[] data) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[data.length];

        q.offer(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            int now = q.poll();
            for (int next : graph.get(now)) {
                if (!visited[next]) {
                    visited[next] = true;           // 방문 처리
                    data[next] = data[now] + 1;     // 거리 갱신
                    q.offer(next);                 // 큐에 추가
                }
            }
        }
        return data;
    }

}

 

 

 

내가 초기에 제출한 dfs 풀이 (시간 초과)

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;

        List<List<Integer>> graph = new LinkedList<>();
        int[] data = new int[n + 1];
        boolean[] visited = new boolean[n + 1];

        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new LinkedList<>());
        }

        // 간선 양방향 연결
        for (int[] next : edge) {
            int first = next[0];
            int second = next[1];
            graph.get(first).add(second);
            graph.get(second).add(first);
        }

        data[1] = 0;  // 시작 노드
        dfs(1, graph, data, visited);

        // 가장 큰 거리 구하기
        int max = 0;
        for (int d : data) {
            max = Math.max(max, d);
        }

        // 가장 먼 노드 개수 세기 (스택 방식 유지)
        Stack<Integer> result = new Stack<>();
        for (int d : data) {
            if (result.isEmpty()) {
                result.push(d);
            } else {
                if (result.peek() < d) {
                    result.clear();
                    result.push(d);
                } else if (result.peek() == d) {
                    result.push(d);
                }
            }
        }

        return result.size();
    }

    public void dfs(int start, List<List<Integer>> graph, int[] data, boolean[] visited) {
        visited[start] = true;

        for (int next : graph.get(start)) {
            // 더 짧은 거리로 갈 수 있다면 다시 방문
            if (!visited[next] || data[next] > data[start] + 1) {
                data[next] = data[start] + 1;
                dfs(next, graph, data, visited);
            }
        }
    }
}

 

 

 

 

문제에서 양방향이고  그래프이고 최단거리를 구하는 문제였다.

 

내가 착각하고 dfs로 접근하였는데 이 문제를 계기로 그래프와 최단거리에서 bfs 선택에 대한 기반이 잡혀진거 같다.