프로그래머스(가장 먼 노드, LV3)

문제 내용

문제 설명

입출력 예시

---

제출한 코드

import java.util.*;

public class Solution {

    static ArrayList<Integer>[] list;
    static int[] visited;
    static int max = 0;

    public int solution(int n, int[][] edge) {
        initData(n, edge);
        return getAnswer();
    }

    private void initData(int n, int[][] edge) {
        list = new ArrayList[n + 1];
        visited = new int[n + 1];
        max = 0;

        for (int i = 0; i < list.length; i++) {
            list[i] = new ArrayList<>();
        }

        for (int[] arr : edge) {
            int node1 = arr[0];
            int node2 = arr[1];

            list[node1].add(node2);
            list[node2].add(node1);
        }
    }

    private int getAnswer() {
        int answer = 0;
        bfs(1, 1);

        for (int i : visited) {
            if (i == max) {
                answer++;
            }
        }
        return answer;
    }

    private void bfs(int start, int count) {
        Queue<Integer> q = new LinkedList();
        q.add(start);
        q.add(count);
        visited[start] = count;

        while (!q.isEmpty()) {
            int node = q.poll();
            int n = q.poll();

            if (max < n) {
                max = n;
            }

            for (int i = 0; i < list[node].size(); i++) {
                int next = list[node].get(i);

                if (visited[next] != 0) {
                    continue;
                }

                visited[next] = n + 1;
                q.add(next);
                q.add(n + 1);
            }
        }
    }
    
}

---

후기

그래프 탐색 문제는 내가 3학년때 처음 알고리즘 강의를 수강했었을때 처음 접했었고, 오랜만에 풀어보는 문제였다
평소에 그래프 탐색 문제를 좀 더 연습하고 싶다고 생각만 가지고있다가 풀어봤던 문제다

 

위 입출력 예시에도 나와있듯이 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하라는 건데, 처음엔 단순히 거리가 먼 노드가 하나만 있을 거라 생각하긴 했었다. 예제에서도 마찬가지로 4, 5, 6처럼 여러 개가 나올 수 있다는 걸 보고 “최대 거리인 노드가 몇 개인지를 구하는 문제구나” 하고 접근했다

 

처음엔 재귀 DFS로 접근해볼까 했지만, 최단 경로를 기준으로 가장 먼 노드를 찾는 문제이기 때문에 알고리즘 시간에 배웠었던 BFS를 적용해서 풀이했다

---

추가적으로 학습한 내용

노드를 방문할 때마다 그 노드까지 걸린 “거리”를 기록해두고, 방문이 끝난 뒤 visited 배열에서 가장 큰 값 을 찾아주고 그 거리를 가진 노드의 개수를 세는 방식으로 풀었다

for (int i : visited) {
    if (i == max) answer++;
}

풀고나서 다른 사람들의 풀이를 보고 추가적으로 깨달은 내용도 있었는데, 나는 BFS에서는 (노드 번호, 거리) 를 같이 관리해야 해서 큐에 두 값을 번갈아 넣는 구조로 했었다. 근데 Pair나 Node 클래스를 적용하면 훨씬 간결하고 풀이 내용을 떠올리기도 쉬울거같아서 더 깔끔하게 풀이할 수 있을거같다는 생각이 들었다

 

시험기간이라 알고리즘에 소홀했었는데.... 시험 끝나고 다른 포스팅으로 다시 돌아오도록 하겠다