[프로그래머스 / Level3] 가장 먼 노드 (Java)

문제 보기

BFS로 찾은 경로는 최단 경로이다.

풀이

• 그래프의 한 정점(1)에서 다른 정점들의 최단 거리를 구하기 위하여 BFS 사용
• 가장 먼 정점들의 수를 구하기 위하여 answer, maxPath 변수 사용
  
  
• 정점들의 거리를 계산하기 위하여 edges, paths, visited 를 사용
• 간선들의 정보인 edges 에 startVertex 가 존재하면, nextVertex 를 방문 안한경우만(!visted) 탐색
• 정점들의 거리가 maxPath 보다 큰 경우 교체하고 answer 을 1로 초기화, 같은 경우 answer 1 증가
• BFS 끝나면 answer 반환

import java.util.LinkedList;
import java.util.Queue;

class Solution {

    static int[][] edges;
    static int[] paths;
    static boolean[] visited;
    static int answer = 0;
    static int maxPath = 0;

    public int solution(int n, int[][] edge) {
        edges = edge;
        paths = new int[n];
        visited = new boolean[n];

        bfs();

        return answer;
    }

    public void bfs() {
        Queue<Integer> queue = new LinkedList();
        visited[0] = true;
        queue.add(1);
        while (!queue.isEmpty()) {
            int startVertex = queue.remove();
            for (int i = 0; i < edges.length; i++) {
                int nextVertex;
                if (edges[i][0] == startVertex) {
                    nextVertex = edges[i][1];
                } else if (edges[i][1] == startVertex) {
                    nextVertex = edges[i][0];
                } else {
                    continue;
                }

                if (visited[nextVertex - 1]) {
                    continue;
                }

                int nextPath = paths[startVertex - 1] + 1;
                paths[nextVertex - 1] = nextPath;
                if (nextPath > maxPath) {
                    maxPath = nextPath;
                    answer = 1;
                } else if (nextPath == maxPath) {
                    answer++;
                }
                visited[nextVertex - 1] = true;
                queue.add(nextVertex);
            }
        }
    }
}