가장 먼 노드 - Java, Graph, BFS

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

 

코드 & 풀이

 

import java.util.*;

class Solution {
    static class Node {
        int node;
        int count;

        Node(int pre, int count) {
            this.node = pre;
            this.count = count;
        }
    }
    public int solution(int n, int[][] edge) {
        Map<Integer, List<Integer>> graphs = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graphs.put(i, new ArrayList<>());
        }

        for (int[] e : edge) {
            addEdge(graphs, e[0], e[1]);
        }

        int[] max_count = new int[n];
        boolean[] visited = new boolean[n + 1];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1, 0));
        visited[1] = visited[0] = true;

        while(!q.isEmpty()) {
            Node cur = q.poll();

            for (Integer next : graphs.get(cur.node)) {
                if (visited[next]) continue;
                visited[next] = true;
                q.add(new Node(next, cur.count + 1));
                max_count[cur.count + 1]++;
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            if (max_count[i] > 0) return max_count[i];
        }
        return 0;
    }

    static void addEdge(Map<Integer, List<Integer>> graph, int s, int e) {
        graph.get(s).add(e);
        graph.get(e).add(s);
    }
}

 

그냥 별다른 알고리즘은 필요없었음.

 

일단 Map으로 grap를 그림

 

그 후에 BFS 방식으로 1부터 시작해서 다음 노드를 탐색

 

탐색한 길이를 배열로 기록 → 마지막에 역순으로 탐색하면서 0 이상인 위치를 탐색

 

찾으면 반환, 못찾으면 0 반환 (1과 연결된게 없다는 거임.)

 

처음에는

 

BFS 안에서 스탭의 최댓값을 계속해서 구했는데

 

이렇게 하는게 오히려 가독성이 좋음.

 

역할이 명확해짐.

 

반복문 안에서는 노드 탐색만,

 

밖에서는 최대 거리의 노드 탐색만으로

 

역할을 나눌 수 있었음.

 

Lv.3 라고 믿기지 않을정도로 단순한 문제였음.

 

 

다음에 또 봐요