문제 출처

코딩테스트 연습 > 그래프 > 가장 먼 노드
https://school.programmers.co.kr/learn/courses/30/lessons/49189

문제 설명

노드 개수 n, 간선 정보 2차원 배열 vertex, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지 return 하라

접근 방법

문제의 접근은 BFS 이다.
각각 노드 마다 어떤 노드가 연결되어있는지에 대한 graph를 생성한다. 그리고 노드별 방문 여부 visited를 생성한다.

BFS를 통해 현재 탐색ㄷ할 레벨의 노드 만큼 탐색을 진행하여 큐에 삽입하는 것을 반복한다. 더 이상 큐에 삽입할 수 있는 노드가 없게 되면 이는 가장 먼 노드들의 개수가 된다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        
        int answer =0;
        List<List<Integer>> graph = new ArrayList<>();
        boolean visited[] = new boolean[n+1];
        
        for(int i = 0; i<=n; i++){
            graph.add(new ArrayList<>()); // 그래프 초기화(노드의 번호가 1번부터 이므로 번호를 맞추기위해 0~n까지 총 n+1개)
        }
        
        for(int i = 0; i<edge.length; i++){
            graph.get(edge[i][0]).add(edge[i][1]); // 양방향 그래프
            graph.get(edge[i][1]).add(edge[i][0]);
        }
        
        for(int i = 1; i<=n; i++){
            Collections.sort(graph.get(i));
        }
        
        //bfs
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        visited[1] = true;
        int que_size, node;
        
        while(!queue.isEmpty()){
            que_size = queue.size();// 현재 탐색할 레벨의 노드 개수 저장
            for(int i = 0; i<que_size; i++){ // 현재 탐색할 레벨의 노드 개수 만큼만 반복(단계별)
                node = queue.poll(); 
                for(int j = 0; j<graph.get(node).size(); j++){
                    if(visited[graph.get(node).get(j)] == false){
                        visited[graph.get(node).get(j)] =true;
                        queue.offer(graph.get(node).get(j));
                    }
                }
            }
            answer= que_size; // 마지막에 도착할 경우 다음엔 q가 비어있으므로 que_size가 가장 먼 노드의 갯수이다.
        }
        return answer;
    }
}

Review

import java.util.*;

class Solution {
    static boolean[] visited;

    static List<List<Integer>> graph;

    public int bfs(int n, int[][] edge, int start){
        Queue<Integer> q = new LinkedList<>();
        int count = 0;
        q.add(start);
        visited[start] = true;
        while(!q.isEmpty()){
            // 노드 레벨 처리
            count = q.size();

            for(int i =0; i<count; i++){
                int point = q.poll();
                for(int j = 0; j<graph.get(point).size(); j++){
                    if(visited[graph.get(point).get(j)]) continue;
                    visited[graph.get(point).get(j)] = true;
                    q.offer(graph.get(point).get(j));
                }
            }
        }
        return count;
    }
    public int solution(int n, int[][] edge) {
        int answer = 0;
        // 방문 여부 확인
        visited = new boolean[n+1];

        Arrays.sort(edge,(a,b) ->Integer.compare(a[0],b[0]));

        //양방향 그래프 생성
        graph = new ArrayList<>();

        for(int i = 0; i<=n; i++){
            graph.add(new ArrayList<>());
        }

        for(int j = 0; j<edge.length; j++){
            graph.get(edge[j][0]).add(edge[j][1]);
            graph.get(edge[j][1]).add(edge[j][0]);
        }

        answer =bfs(n,edge,1);
        return answer;
    }
}

알게된 점

처음 풀이할 때, visited를 간선의 정보로 선택하여 풀려했지만 이는 잘 풀리지 않았다.

이 문제의 가장 중요한 부분이

que_size = queue.size();// 현재 탐색할 레벨의 노드 개수 저장

해당 부분이라고 생각한다. 현재 탐색할 레벨들을 점차 지나가면서 점점 더 멀리 있는 노드들을 탐색할 수 있게하기 때문이다.
출처
https://arinnh.tistory.com/40

문제푼 흔적

Review