99클럽 코테 스터디 24일차 TIL [BFS]

- 오늘의 학습 키워드 : bfs

[문제 이름 : 가장 먼 노드 (프로그래머스, Lv 3) ]

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

 

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    static ArrayList<Integer>[] list;
    static boolean[] visited;
    public int solution(int n, int[][] edge) {
        list = new ArrayList[n+1];
        visited = new boolean[n+1];
        
        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i=0; i<edge.length; i++) {
            int start = edge[i][0];
            int end = edge[i][1];
            list[start].add(end);
            list[end].add(start);
        }
        
        return bfs();
    }
    
    static int bfs() {
        // 1번과 떨어져 있는 깊이
        int depth = 0;
        // 1번과 제일 멀리 떨어져 있는 깊이
        int maxDepth = 0;
        int count = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {1,depth});
        visited[1] = true;
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            int endNode = now[0];
            depth = now[1];
            
            // 현재 노드 거리가 최대 노드 거리보다 큰 경우, maxDepth와 count 갱신
            if (depth > maxDepth) {
                maxDepth = depth;
                count = 1;
            } else if (depth == maxDepth) {
                count++;
            }
            
            // bfs 탐색
            for(int num : list[endNode]) {
                if(!visited[num]) {
                    queue.add(new int[] {num, depth+1});
                    visited[num] = true;
                }
            }
        }
        return count;
    }
}​

[풀이 과정]

1. 무방향 그래프이므로, 시작 노드와 끝 노드를 기준으로 ArrayList배열을 선언하고, 해당 값을 저장한다.

2. bfs로 너비 우선 탐색을 하며, depth를 순차적으로 더해가며 queue에 더한다.
3. queue에서 나온 배열은 [0]이 Node, [1]이 깊이를 의미한다. 이때 현재 깊이가 최대 깊이보다 크다면, 깊이를 갱신해주고, 최대 깊이의 노드 개수를 1로 갱신한다. 그렇지 않고 현재 깊이가 최대 깊이와 동일한 경우, 최대 깊이의 노드 개수를 1 더해준다.

bfs에 대한 개념이 있다면, 어렵지 않게 풀 수 있는 문제였다.

풀이 시간 : 30분

 

내일은 백준의 'BaaaaaaaaaaarkingDog' 이라는 분께서 만드신 알고리즘 문제집을 순차적으로 풀어보려고 한다.