99클럽 코테 스터디 24일차 TIL / [프로그래머스] 가장 먼 노드

오늘의 학습 키워드

---

BFS, 그래프

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 가장 먼 노드
• 난이도: Lv3

풀이

---

import java.util.*;

class Solution {
    
    static List<List<Integer>> adjList = new ArrayList<>();
    static boolean[] visited;
    
    public int solution(int n, int[][] edge) {
        visited = new boolean[n + 1];
        
        for(int i=0; i<=n; i++) {
            adjList.add(new ArrayList<>());
        }
        
        for(int[] adj : edge) {
            int node1 = adj[0];
            int node2 = adj[1];
            
            adjList.get(node1).add(node2);
            adjList.get(node2).add(node1);
        }
        
        return bfs(1);
    }
    
    public int bfs(int node) {
        int maxDist = 1;
        int answer = 0;
        int dist = 1;
        
        Queue<Integer> queue = new LinkedList<>();
        visited[node] = true;
        
        for(int movable : adjList.get(node)) {
            visited[movable] = true;
            maxDist = dist;
            answer++;
            queue.offer(movable);
        }
        
        while(!queue.isEmpty()) {
            dist++;
            int size = queue.size();
            
            for(int i=0; i<size; i++) {
                int curNode = queue.poll();
                
                for(int movable : adjList.get(curNode)) {
                    if(!visited[movable]) {
                        if(maxDist < dist) {
                            answer = 0;
                        }
                        maxDist = dist;
                        answer++;
                        visited[movable] = true;
                        queue.offer(movable);
                    }
                }
            }
        }
        return answer;
    }
}

접근

• BFS를 활용하면 간단히 구현할 수 있는 문제였습니다.
• 시작 노드로부터 최장 거리의 노드의 개수를 리턴해야 하기에, BFS 로직 내부에서 거리를 계산하고 비교하여 최대인 경우 그 수를 카운트했습니다.

소요 시간

30분