[프로그래머스] 가장 먼 노드 (Java) / BFS

문제

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

코딩테스트 연습 - 가장 먼 노드

풀이

해당 문제는 노드의 개수가 2 이상 20,000 이하로 매우 큰 편이다. 때문에, 제일 깊은 노드까지 갔다가 다시 돌아와서 다른 노드를 살펴보는 깊이우선탐색(DFS) 보다는 넓이 위주로 탐색하면서 마지막 깊이의 노드들의 개수를 반환하는 방식의 BFS 방식이 효율적이다.

또한 2차원 배열을 사용해 O(N^3) 시간 복잡도를 가지는 플로이드 와샬 풀이도 메모리 초과가 난다.

BFS 코드

import java.util.*;
import java.io.*;

class Solution {
    static ArrayList<ArrayList<Integer>> list;
    public int solution(int n, int[][] edge) {
        int answer = 0;
        list = new ArrayList<>();
        for(int i=0; i<= n; i++) {
            list.add(i, new ArrayList<>());
        }
        
        for(int i=0; i < edge.length; i++) {
            int a = edge[i][0];
            int b = edge[i][1];
            list.get(a).add(b);
            list.get(b).add(a);
        }
        
        answer = bfs(1, n);
        return answer;
    }
    
    private static int bfs(int start, int n) {
        int answer = 0;
        Deque<Integer> deque = new ArrayDeque<Integer>();
        boolean[] visited = new boolean[n+1];
        deque.add(start);
        visited[start] = true;
        
        while(true) {
            Deque<Integer> temp = new ArrayDeque<Integer>();
            
            while(!deque.isEmpty()) { // 같은 깊이의 노드 수 만큼만 반복
                int value = deque.poll();
                
                for(int node: list.get(value)) { // value와 인접한 모든 노드들
                    if(!visited[node]) {
                        temp.add(node); // deque가 아니라 temp에 담기!
                        visited[node] = true;
                    }
                }
            }
            
            if(temp.isEmpty()) break; // 더 깊은 깊이에 노드가 없다는 뜻
            answer = temp.size(); // temp.size()는 현재 살펴본 가장 깊은 깊이에 있는 노드의 개수
            while(!temp.isEmpty()) { 
	            // temp에 있는 노드의 다음 깊이를 살펴보기 위해 deque에 temp를 모두 add
                deque.add(temp.poll());
            }
        }
        return answer;
    }
}

 

bfs함수에서 두번째 while문의 deque에는 항상 같은 깊이를 갖는 노드들이 담겨있다. 또한, 그 깊이는 점점 깊어진다.

예를 들어, 그래프가 아래와 같다면

처음 while문에 진입할 때, deque에 담긴값 (깊이 0)은 1 하나이다.

deque를 비우고 두번째 while문이 다시 실행될때마다

deque에 담긴값 (깊이 1):  2,3 -> deque에 담긴값 (깊이 2):  6,4,5

으로 변화한다.

 

이것이 가능한 이유는 temp라는 deque를 하나 더 사용하기 때문이다. temp에는 항상 현재 살펴본 가장 깊은 깊이의 노드들만 담기게 된다. 그 코드가 바로 아래에 해당된다.

for(int node: list.get(value)) { // value와 인접한 모든 노드들
  if(!visited[node]) {
	temp.add(node); // deque가 아니라 temp에 담기!
  	visited[node] = true;
  }
}

현재 deque에 담겨있는 모든 value가 같은 깊이를 가지고 있고, temp에는 그 value들의 다음 깊이 노드들만 담는다.

때문에 temp에는 현재 살펴본 깊이 중 가장 깊은 깊이의 노드들만 담기는 것이다.

 

결론적으로, deque가 비었을 때 temp가 비어있다면 이는 바로 이전에 temp에 담겼었던 노드가 가장 깊은 깊이의 노드인 것이므로 break; 하여 while문을 빠져나간 후, 이전 temp의 size가 이미 담겨있는 answer를 반환하면 된다.

 

내일은 다익스트라로 풀어 보자!