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

오늘의 학습 키워드

   - 알고리즘

   - 그래프 탐색

   - 너비 우선 탐색

공부한 내용 본인의 언어로 정리하기

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

BFS를 활용한 문제를 풀었다.

 

풀이 과정은 다음과 같다.

1. visit 배열을 boolean이 아닌 int 값으로 선언

2. bfs 로직을 돌며 방문 처리를 이전 방문 거리 + 1로 visit 배열에 할당

3. 마지막에 반복문을 돌며 가장 먼 노드가 몇 개인지 카운트

 

풀이는 다음과 같다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        
        ArrayList<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        
        for (int[] line : edge) {
            graph[line[0]].add(line[1]);
            graph[line[1]].add(line[0]);
        }
        
        int[] visit = new int[n + 1];
        visit[1] = 1;
        
        Deque<Integer> que = new ArrayDeque<>();
        que.add(1);
        
        while(!que.isEmpty()) {
            int cur = que.pollFirst();
            for (int next : graph[cur]) {
                if (visit[next] != 0) continue;
                visit[next] = visit[cur] + 1;
                que.addLast(next);
            }
        }
        
        int answer = 0;
        int maxDist = 0;
        
        for (int i = 1; i <= n; i++) {
            if (visit[i] == maxDist) answer++;
            else if (visit[i] > maxDist) {
                answer = 1;
                maxDist = visit[i];
            }
        }
        
        return answer;
    }
}