(Java) 너비 우선 탐색 순회 - BFS 구현 (큐)

 

📑 1. 문제설명

최단 경로를 보장하는 문제에서 너비 우선탐색을 한다. 너비 우선탐색을 큐로 구현해보자.

• 너비 우선 탐색으로 모든 노드를 순회하는 함수 solution()을 작성하기
• 시작노드는 매개변수 start로 주어진다. 
• graph는 (출발 노드, 도착 노드) 쌍들이 들어 있는 리스트이다. 
• 반환값은 그래프의 시작 노드부터 모든 노드를 너비 우산 탐색으로 진행한 순서대로 노드가 저장된 리스트이다. 

 

제약 조건

• 노드의 최대 개수는 100개이다.
• 시작 노드부터 시작해서 모든 노드를 방문할 수 있는 경로가 항상 있다.
• 그래프의 노드는 숫자이다.

입출력 예

graph	start	n	return
[[1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7], [4, 8], [5, 8], [6, 9]]	1	9	[1, 2, 3, 4, 5, 6, 7, 8, 9]
[[1, 3], [3, 4], [3, 5], [5, 2]]	1	5	[1, 3, 4, 5, 2]

 

---

💡 2. 풀이과정

1. 큐가 비었는지 확인하기
   1. 큐가 비어 있다면 방문할 수 있는 모든 노드를 방문했기 때문에 탐색 종료
2. 큐에서 노드를 poll
3. poll한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드를 큐에 add하며 방문처리

이 때 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 한다

이미방문한 노드인지 확인할 수 있어야 한다.

---

👨‍💻 3. 정답코드

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    
    // 인접 리스트를 저장할 ArrayList 배열 선언
    private static ArrayList<Integer>[] adjList;
    
    // 방문 여부를 저장할 boolean 배열
    private static boolean[] visited;
    private static ArrayList<Integer> answer;
    
    private static int[] solution(int[][] graph, int start, int n) {
        adjList = new ArrayList[n + 1];
        for (int i = 0; i < adjList.length; i++) {
            adjList[i] = new ArrayList<>();
        }
        
        for (int[] edge : graph) {
            adjList[edge[0]].add(edge[1]);
        }
        
        // 방문 여부 저장할 배열
        visited = new boolean[n + 1];
        answer = new ArrayList<>();
        
        // 시작 노드부터 너비 우선 탐색 시작
        bfs(start);
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
    
    // BFS 탐색 메서드
    private static void bfs(int start) {
        // 탐색시 맨 처음 방문할 노드를 add하고 방문 처리
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        visited[start] = true;
        
        // 큐가 비어 있지 않은 동안만
        while(!queue.isEmpty()) {
            // 큐에 있는 원소 중 가장 먼저 추가된 원소를 poll하고 정답 리스트에 추가
            int now = queue.poll();
            answer.add(now);
            // 인접한 이웃 노드 탐색
            for (int next : adjList[now]) {
                if (!visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }
    public static void main(String[] args) {
        // 테스트용 그래프: 간선 배열 [from, to]
        int[][] graph = {
            {1, 2},  {1, 3},
            {2, 4},  {3, 5},
            {4, 6},  {5, 6}
        };

        int start = 1; // BFS 시작 노드
        int n = 6;     // 노드 개수

        int[] bfsOrder = Solution.solution(graph, start, n);

        System.out.println("BFS 탐색 순서:");
        System.out.println(Arrays.toString(bfsOrder));
    }
}

 

adjList는 그래프를 인접 리스트로 표현하기 위한 변수이다.

그리고 visited의 목적은 한 번 방문한 노드를 체크해서 다시 방문하지 않도록 하는 것이다.

1. 시작 노드부터 너비 우선 탐색을 할 수 있도록 큐에 시작 노드를 넣고 방문처리 한다.
2. ArrayDeque의 add() 메서드와 poll() 메서드를 이용하면 큐와 동일하게 사용할 수도 있다.
3. 시작 노드를 기준으로 너비 우선 탐색을 진행한다. 큐가 비는 시점, 즉, 방문할 수 있는 모든 노드에 방문할 때 까지 탐색을 진행한다.
4. 현재 poll 한 노드를 answer 리스트에 add하고, 인접 노드들을 방문한다.
5. node와 인접한 노드들을 순회하며 인접한 노드 중 방문하지 않은 노드가 있다면 해당 노드를 방문 처리하고 add한다.