프로그래머스 가장 먼 노드(lvl3) 풀어보기

문제링크

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

프로그래머스

---

문제 핵심

1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

---

문제 풀이법

-큐에기본 1할당

1의 이어진 노드부터 출발

이어진노드들 방문(true처리)

최고로 멀리왔는지 확인

아니라면 숫자 카운트

맞다면 최고먼거리 재설정

카운트 1로 초기화

반복

---

제출코드

public static int solution(int n, int[][] edge) {

        int answer = 0;

        Map<Integer, List<Integer>> roots = new TreeMap<>();

        for (int i = 0; i < edge.length; i++) {

            int a = edge[i][0];

            int b = edge[i][1];

            roots.putIfAbsent(a, new ArrayList<>());

            roots.putIfAbsent(b, new ArrayList<>());

            roots.get(a).add(b);

            roots.get(b).add(a);

        }

        System.out.println(roots);

        boolean[] visited = new boolean[n + 1];

        visited[1] = true;

        Queue<int[]> queue = new LinkedList<>();

        queue.add(new int[] { 1, 0 });

        int max = 0;

        int maxc=0;

        while (!queue.isEmpty()) {

            System.out.println(queue.stream().map(Arrays::toString).toList());

            int[] nextInfo = queue.poll();

            int ismax = nextInfo[1];

            if(ismax>max){

                max=ismax;

                maxc=1;

            }else if(ismax==max){

                maxc+=1;

            }

            List<Integer> nexts = roots.get(nextInfo[0]);

            for (int next : nexts) {

                if (!visited[next]) {

                    visited[next] = true;

                    queue.add(new int[] { next, nextInfo[1] + 1 });

                }

            }

        }

        answer=maxc;

        System.out.println(answer);

        return answer;

    }

 

---

결과

---

gpt피드백

-

1. 알고리즘 평가

평가

최종 알고리즘은 정확해.

알고리즘 개선점

사실 지금도 충분히 좋은데, 하나 개선할 수 있어.

현재는 큐에:

int[]{node, distance}

두 값을 저장하고 있어.

그런데 BFS는 레벨 단위로 처리할 수도 있어.

예를 들어:

queue = [1]        → 거리 0

queue = [2,3]      → 거리 1

queue = [4,6]      → 거리 2

queue = [5]        → 거리 3

현재 큐의 size()만큼 처리하면 그게 정확히 같은 거리의 노드들이야.

그러면 각 노드마다 거리를 같이 들고 다닐 필요가 없어.

2. 코드 평가

평가

코드 전체적으로 꽤 잘 짰어.

코드 개선점 1 — TreeMap은 필요 없음

현재:

Map<Integer, List<Integer>> roots = new TreeMap<>();

그런데 이 문제에서는 노드를 정렬된 순서로 탐색할 필요가 없어.

 

 

 

---

후기

-어우 처음에 dfs로 구현했다가

헤맸다 이문제로 언제 dfs/bfs를 써야할지 조금더 

명확해진거같다