그래프 - 너비 우선 탐색 순회

그래프(Graph)란?

그래프는 정점(Node) 과 이 정점들을 연결하는 간선(Edge) 으로 이루어진 자료 구조

• 정점(Node): 각각의 지점 또는 데이터를 표현
• 간선(Edge): 정점 간의 연결 관계를 표현

그래프는 다음 두 가지로 나뉠 수 있다.

• 무방향 그래프(Undirected Graph): 간선에 방향성이 없는 그래프
• 방향 그래프(Directed Graph): 간선에 방향이 있는 그래프

보통 너비 우선 탐색을 할 때는 무방향 또는 방향 모두 가능하다.

---

그래프 탐색이란?

그래프 탐색은 그래프 내의 정점들을 방문하는 알고리즘이다. 주로 사용하는 두 가지 탐색 방식이 있다.

• 깊이 우선 탐색(Depth-First Search, DFS)
  • 가능한 한 깊이 들어가며 탐색 후 끝에서부터 돌아와 다른 길 탐색
• 너비 우선 탐색(Breadth-First Search, BFS)
  • 시작 정점과 가까운 정점부터 차례대로 탐색

---

너비 우선 탐색(BFS)의 개념 및 특징

너비 우선 탐색(BFS)는 큐(Queue) 라는 자료구조를 사용해 탐색한다.

• 큐는 먼저 들어간 데이터가 먼저 나오는(FIFO, First-In-First-Out) 구조를 가진 자료 구조이다.

1. 시작 노드를 방문하고 큐에 넣는다.
2. 큐에서 노드를 하나씩 꺼내면서 꺼낸 노드와 인접한 노드 중 방문하지 않은 노드를 방문하고 큐에 넣는다.
3. 큐가 빌 때까지 반복한다.

BFS는 시작 노드와 가까운 순서대로 탐색한다.

출처: https://images.velog.io/images/polynomeer

---

너비 우선 탐색(BFS)의 장점

• 최단 경로를 찾을 때 유용하게 사용된다.
• 가까운 노드부터 단계별 탐색하기 때문에 모든 노드 방문 여부나 연결 요소 확인에도 사용이 가능하다.

---

문제 35: 너비 우선 탐색 순회

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

제약 조건

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

입출력의 예

graph	start	n	return
[[1, 2], [1, 3], [2, 4], (2, 5], [3, 6], [3, 7J, [4, 81, [5, 81, [6, 9, [7, 9]]	1	9	[1, 2, 3, 4, 5, 6, 7, 8, 91
[[1, 3], [3, 4], [3, 5], [5, 2]]	1	5	[1, 3, 4, 5, 2)

※ 이 문제는 탐색 순서에 따라 정답이 여러 개일 수 있습니다

풀이

• 주어진 시작 노드에서 BFS를 수행하여 그래프의 모든 노드를 방문하고 노드 방문 순서를 반환해야 한다.
• 입력으로는 그래프를 구성하는 노드 쌍(간선)과 시작 노드(start)가 주어진다.

import java.util.ArrayDeque;
import java.util.ArrayList;

class Solution {
    // 인접 리스트를 저장하는 ArrayList 배열
    // 각 노드의 인접한 노드 목록을 저장한다.
    private static ArrayList<Integer>[] adjList;

    // 방문 여부를 저장할 boolean 배열
    // 노드를 방문하면 해당 인덱스를 true로 변경
    // 한 번 방문한 노드를 체크해서 다시 방문하지 않도록 함
    private static boolean[] visited;

    // 방문한 노드의 순서를 저장하는 리스트
    private static ArrayList<Integer> answer;

    private static int[] solution(int[][] graph, int start, int n) {
        // 1. 그래프 초기화
        adjList = new ArrayList[n + 1];
        for (int i = 0; i < adjList. length; i++) {
            // 각 노드마다 빈 ArrayList 생성
            adjList[i] = new ArrayList<>();
        }
        for (int[] edge : graph) {
            // 각 노드의 연결 상태 표현
            adjList[edge[0]].add(edge[1]);
        }
        // edge = [1, 2]  → adjList[1].add(2)
        // edge = [1, 3]  → adjList[1].add(3)
        // edge = [2, 4]  → adjList[2].add(4)
        // edge = [3, 5]  → adjList[3].add(5)
        // edge = [4, 5]  → adjList[4].add(5)

        // adjList[1] → [2, 3]
        // adjList[2] → [4]
        // adjList[3] → [5]
        // adjList[4] → [5]
        // adjList[5] → []

        // 2. 방문 목록 초기화
        visited = new boolean[n + 1];
        answer = new ArrayList<>();

        // 3. 시작 노드에서 너비 우선 탐색 시작
        bfs(start);

        // 4. 결과 리턴
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }

    // bfs
    private static void bfs(int start) {
        // 탐색 순서를 관리하는 큐
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            // 큐에서 노드를 꺼내 방문 순서에 추가
            int now = queue.poll();
            answer.add(now);

            // 인접한 노드가 존재 시 방문 + 큐에 추가
            for (int next : adjList[now]) {
                if (!visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }
}

---

너비 우선 탐색(BFS, Breadth-First Search)은 1959년에 Edward F. Moore가 처음으로 공식적으로 제안했어.

📌 누가, 언제 만들었을까?

• Edward F. Moore (에드워드 F. 무어)
  • 미국의 수학자 겸 컴퓨터 과학자
  • 1959년에 너비 우선 탐색을 소개
  • 본래 목적은 미로(maze)에서 최단 경로를 찾기 위한 알고리즘을 제시하기 위함이었어.

당시 무어는 전자회로의 논리 설계 및 경로 찾기 문제를 해결하기 위해 이 알고리즘을 처음 고안했는데, 이것이 오늘날 우리가 쓰는 BFS의 시초가 되었어.

📚 원본 논문 정보

• "The shortest path through a maze" (미로에서 최단 경로 찾기, 1959)
  • 미로 문제를 해결하기 위한 알고리즘으로 BFS 소개
  • 각 지점에서 가까운 노드를 순차적으로 탐색하는 방식이었어.

🔍 왜 BFS를 만들었을까?

당시 컴퓨터 과학 초창기엔 효율적인 최단 경로 탐색 알고리즘이 필요했어.
미로나 그래프 같은 구조에서 최단 경로를 빠르게 찾는 문제가 흔히 발생했고, BFS는 이러한 문제를 해결하기 위한 효과적인 접근법이었지.

🎯 BFS의 현재 중요성

오늘날 BFS는 다음과 같은 다양한 문제에 폭넓게 쓰이고 있어:

• 최단 경로 찾기
• 네트워크나 그래프에서 가까운 노드 탐색
• 웹 크롤러(인터넷에서 링크를 따라 페이지를 탐색하는 프로그램)
• 소셜 네트워크 분석(가까운 친구, 추천 친구 찾기 등)
• 미로 문제, 퍼즐 등 게임의 경로 탐색