[프로그래머스] 가장 먼 노드-JAVA

문제 링크

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

코딩테스트 연습 - 가장 먼 노드

 

 풀이 과정

 

문제에 주어진 그림을 보자 마자 바로 그래프 자료구조로 접근했다.

 

https://born2bedeveloper.tistory.com/42

[JAVA] 그래프 구현하기 (인접 행렬, 인접 리스트)

그래프를 구현방식을 모른다면 해당 포스트를 간단히 읽고 오도록 하자. (조회수좀..ㅎㅎ)

 

인접 리스트를 통해 주어진 그래프를 그림과 같이 구현한다.

문제가 요구하는 것은 "1"번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 것이다.

따라서 필자는 BFS를 이용하여 모든 노드를 방문하며, 각 노드와 노드 1 사이의 거리를 구할 것이다.

 

1. distance[n+1]을 선언한다 : 1번 노드와의 거리를 담는 배열

2. BFS : 1번 노드부터 시작해 주위 인접 노드를 방문한다.

3. 방문한 2, 3번 노드는 노드 1에서 1만큼 떨어져 있으므로 distance[2] = 3, distance[3] = 3이다.
   이미 방문했으니 해당 노드는 visited[2] = true, visited[3] = true로 방문표시한다.

4. 2번 노드에서 인접한 5번 4번 노드를 탐색한다. 이들은 각각 1에서 2만큼 떨어져있다.
   distance[5] = 2, distance[4] = 2로 설정하고 visited 표기

5. 3번 노드에서 인접한 6번 노드를 살펴본다 (4번노드는 이미 방문했으므로 재탐색 x)
   distance[6] = 2로 설정한다.

6. distance를 오름차순으로 정렬한다. 가장 맨 끝값 (1과 가장 먼 노드의 거리)을 max로 두고 max와 같은 크기의 distance를 센다.

7. 센 개수를 answer로 반환한다.

 

 코드 구현

 

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        int[] distance = new int[n + 1];
        
        for (int i = 0; i < n + 1; i++)
            graph.add(new ArrayList<>());
        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]);
        }
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        Queue<Integer> bfs = new LinkedList<>();
        bfs.add(1);
        while (bfs.size() != 0) { // 2~n까지 도착하는 경로 구하기
            int nowNode = bfs.poll();
            ArrayList<Integer> node = graph.get(nowNode);
            for(int i = 0; i < node.size(); i++) {
                if (visited[node.get(i)] == false) {
                    bfs.add(node.get(i));
                    visited[node.get(i)] = true;
                    distance[node.get(i)] = distance[nowNode] + 1; 
                }      
            }  
        }
        Arrays.sort(distance);
        int max = distance[distance.length-1];
        for(int i = distance.length-1; distance[i] == max; i--)
            answer++;
        return answer;
    }
}

 

그래프 구현과 BFS를 알고있다면 편하게 풀 수 있는 문제다.

만약 둘 다 익숙하지 않은 개념이라면 먼저 각 방식을 공부하고 다시 오는 것을 추천한다.