BFS (Breath-First-Search, 너비 우선 탐색) 은 시작점에 인접한 다른 정점을 모두 방문하고, 다른 정점에 대해서도 인접한 또 다른 정점을 모두 방문하는 방법입니다.

여기서, 인접하다는 의미는 두 정점이 하나의 간선으로 연결되어 있다는 의미입니다.

라고.. 저는 누가 물어보면 말할래요 ~찡긋

그림을 통해 설명드리겠습니다.

그림이 낯선 이유? 제가 그렸기 때문이에요

그림은 쥐와 다른 동물 친구들과의 관계를 보여줍니다.

한 동물이 다른 동물과 연결되어있으면 친구 관계입니다.
쥐와 토끼가 친구이고, 토끼와 뱀이 친구이면, 쥐와 뱀도 친구입니다.

1) 쥐가 자신과 연결된 친구들을 방문하고, 친구의 친구를 방문을 계속합니다.
2) 연결을 통해 이동할 때마다 단계가 1증가합니다.
3) 연결되어 있지 않으면 방문할 수 없습니다.

예시와 같이, BFS는 시작점(쥐)에 연결된 친구들을 모두 만나고, 친구들의 모든 연결된 다른 친구들을 모두 만납니다. 계속해서, 쥐와 연결된 모든 친구들을 방문할때 까지 만납니다.

단, 연결되어 있지 않으면 친구가 아니기 때문에 만날 수 없습니다. 양은 만날 수 없습니다.

그렇기 때문에 BFS는 시작점과 연결된 모든 정점들을 방문하는 완전 탐색 입니다.

1. 왜 너비 우선 탐색?

근데, 모든 정점을 탐색할거면 마음대로 탐색할 수 있는데, 왜 너비 우선으로 탐색하냐면요

BFS는 가중치 없는 그래프(간선의 가중치가 모두 1인 그래프)에서 최단 경로를 찾아주기 때문입니다.

최단 경로의 의미는 다음과 같이 여러가지일 수 있습니다.

1. 서울에서 부산으로 가는데 거쳐야하는 최소 정거장의 수
2. 임의의 4자리 숫자 x에서 한자리를 (0~9)로 변경하면 다른 숫자 y를 만들 수 있습니다. 이 때, x에서 z를 만들기 위한 최소 변경 횟수
3. 친구 관계에서의 단계

그림의 예시에서, 쥐와 다른 친구과의 관계에서 간선을 한번 탈때 마다 단계가 1 증가합니다.

그러면 쥐의 친구 관계는 다음과 같이 나타낼 수 있습니다.

양은 쥐의 친구가 아니기 때문에, 최단 경로가 없습니다.

따라서, 최단 경로가 없다는 의미는, 방문할 수 없다는 의미와 같습니다.

2. 그럼 어떻게 인접한 점을 우선 방문?

너비 우선으로 탐색하기 위해서 일반적으로 큐(queue) 라는 자료구조를 사용합니다.
큐는 먼저 들어간 요소가 먼저 나옵니다.

무언가를 먼저 넣었을때 먼저 나오는 것의 예시에는 다음이 있습니다.

1) 편의점에서 계산하기 위해 줄을 섰고, 줄을 선 순서대로 계산을 합니다.
2) 롤을 하기 위해 큐를 잡고 큐를 잡은 순서대로 게임이 잡힙니다.

그림과 같이 시작점을 포함해서 인접한 정점들을 방문할때마다 차례대로 큐에 넣고, 빼면서 인접한 점을 우선 큐에 넣습니다. (단, 이미 방문한 점은 큐에 넣지 않습니다.)

3. 연결된걸 어떻게 저장?

BFS를 하려면 해야할것이 있습니다.
바로, 그래프 모델링

그래프는 정점(vertex, node)와 간선(edge)로 이루어진 자료구조입니다.
위의 그림은 1) 동물(정점) 과 2) 친구 관계(간선)로 이루어진 그래프입니다.

그림을 어떻게 프로그래밍할것인가요?

그래프 모델링을 하는 방법은 간선을 저장하는 것입니다.

그래프 저장하는 방법은 여러가지가 있는데 1) 인접행렬, 2) 인접리스트가 있습니다.

1) 인접 행렬

시간 복잡도 O(V^2) (v는 정점의 수)

2차원 배열을 사용합니다.
근데 인접행렬 사용하면, 시간이 오래걸리기 때문에 보통 사용안해요
만날일은 거의 없는데, 그리고 그림 그리기 힘드니까 나중에 작성할께요

2) 인접 리스트

시간 복잡도 O(V+E) (v는 정점의 수, E는 간선의 수)

링크드 리스트를 사용합니다.

링크드 리스트 구현하면 좋은 데, 매번 구현하기 귀찮으니까

1) C++에서는 vector
2) java에서는 ArrayList를 사용합니다.

중요한 점은, 쥐의 친구 리스트에는 호랑이가 있고,호랑이의 친구 리스트에도 쥐가 있습니다.

예시와 같이 '방향' 이라는 말이 없으면, 양방향 그래프로 만들어줍니다.
(단방향 또는 유향 그래프라는 말이 있으면, 단 방향으로 만들어 줍니다.)

4. 코드로 어떻게 구현하나요?

문제를 풀면서, 코드를 작성해봅시다.
일반적으로 문제는 다음과 같이 주어집니다.

문제
1부터 n(n은 10000이하) 까지 번호로 이름이 붙여진 정점이 있습니다. 정점들을 간선들로 연결되어 있습니다. 간선을 통해 임의의 정점에서 연결된 정점으로 이동할때 거리가 1씩 증가합니다. 시작점에서 다른 모든 정점들까지 최단거리를 구하세요

입력 정보
첫줄에 n m k 가 한칸씩 공백으로 분리되어 주어집니다.
1) n은 정점의 개수 입니다. 1부터 n까지 n개의 정점이 존재합니다. (1 <= n <= 1만)
2) m은 간선의 개수 입니다. (1 <= m <= 1만)
3) k는 시작점의 번호입니다.

둘째줄부터 m개의 줄에 간선의 정보가 주어집니다. 간선의 정보는 두개의 정수 a b로 표현됩니다. (a와 b는 간선으로 연결되어 있다.)

출력 방법
1~n번까지 각 정점에 대해 최단 거리를 출력하세요.(한 줄씩 줄 바꿈 해서) 단, 방문할 수 없는 정점에 대해서는 -1을 출력하세요

입력값

8 7 1
1 2
2 5
1 3
3 5
7 1
1 4
4 6

출력값

0
1
1
1
2
2
1
-1

c++

처음에는 낯설 수 있어요..
근데 몇번 하다 보면, 손가락이 기억해서 생각 안하고도 짤 수 있어요
(진짜 생각 안하면 안되는거 알죠?)

#include <iostream>
#include <vector>
#include <queue>
// 저는 보통 최대값 + 1을 매크로를 사용해서 선언해줍니다.
// 똑같은 숫자 반복사용하면 오타날때도 있고해서요
// 1증가 시키는 이유는 인덱스 참조하다가 실수 날 수 있어서
#define max_int 10001

using namespace std;

// 저는 보통 다음과 같이 4개의 정보를 주석으로 간단하게 작성해줍니다.
// 그냥, 내가 뭘 만들었는지는 알아먹을수 있어야해서요, 설명할 수는 있어야하잖아요

/*
 시간 복잡도: O(n+m)
 공간 복잡도: O(n)
 사용한 알고리즘: BFS(너비 우선 탐색)
 사용한 자료구조: 인접 리스트, 배열
 */

// check는 최단 거리를 저장할 배열입니다.
int n, m, k, a, b, check[max_int];

// 간선의 정보를 저장할 인접 리스트를 vector로 생성합니다.
vector<int> v[max_int];

// 너비 우선 탐색
void bfs(){
    // 큐를 만들어 줍니다.
    queue<int> q;
    // 시작점까지의 최단 거리는 0입니다.
    check[k] = 0;
    // 큐에 시작점을 넣어줍니다.
    q.push(k);
    
    // 큐가 비어있을때 까지 계속해줍니다.
    // 큐가 비었다는 의미는 시작점에 연결된 모든 다른 정점들을 방문했다는 의미입니다.
    while(!q.empty()){
        // 큐에서 가장 앞에있는것의 정보를 넣어줍니다.
        int node = q.front();
        // 큐 앞에 있는것 비워주는것 꼭 잊지말고요, 빼먹으면, 무한히 돌거에요
        q.pop();
        
        
        // 여기가 중요, 처음에는 낯설어요
        // 임의의 정점에서 연결되 다른 모든 정점들을 next에 넣습니다.
        for(int i=0; i<v[node].size(); i++){
            int next = v[node][i];
            
            // 만약 방문하지 않았다면
            if(check[next] == -1){
                // 여기도 중요! 반드시, 큐에 넣기 전에 방문했음을 체크해줍니다.
                // 여기서 체크안하면 다른 정점이 또 여기를 방문할 수 있습니다.
                // 문제의 예시에서 2 5, 3 5 인데, 2가 먼저 5를 방문했는데 표시 안해주면 3이 또 5를 큐에 넣습니다.
                
                // 간선을 타고 이동할때 마다 1 증가 시키기 때문에 이전 정점까지의 거리에 1을 더해줍니다.
                check[next] = check[node] + 1;
                
                // 다음 정점을 큐에 넣어줍니다.
                q.push(next);
            }
        }
    }
}

int main(){
    // 1. 입력
    // n 정점의 수, m 간선의 수, k 시작점의 번호를 입력 받습니다.
    scanf("%d %d %d", &n, &m, &k);
    
    // 2. 초기화
    // 거리 정보를 저장할 check 배열을 -1로 초기화합니다.
    // 무엇으로 초기화 할지는 개인의 취향입니다.
    for(int i=0; i<=n; i++) check[i] = -1;
    
    // 3. 간선 저장
    for(int i=0; i<m; i++){
        // 간선의 정보를 입력받고
        scanf("%d %d", &a, &b);
        // 중요, 무 방향그래프를 양방향 그래프로 만들어줍니다.
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    // 4. 너비 우선 탐색 수행
    bfs();
    
    // 5. 출력
    for(int i=1; i<=n; i++){
        printf("%d\n", check[i]);
    }
}

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static final int max_int = 10001;
    static int n, m, k, a, b;
    static int[] check = new int[max_int];
    static ArrayList<Integer> v[] = new ArrayList[max_int];

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++) {
            check[i] = -1;
            v[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            v[a].add(b);
            v[b].add(a);
        }

        bfs();

        for(int i=1; i<=n; i++){
            System.out.println(check[i]);
        }
    }

    public static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        check[k] = 0;
        q.add(k);

        while(!q.isEmpty()){
            int node = q.poll();

            for(int i=0; i<v[node].size(); i++){
                int next = v[node].get(i);

                if(check[next] == -1){
                    check[next] = check[node] + 1;
                    q.add(next);
                }
            }
        }
    }
}

5. 경로 추적

시작점에서 도착점까지의 경로를 추적할 수 있습니다.

다음 정점을 방문했을때 이전 정점의 정보를 저장하면 됩니다.

// 위의 코드에서
	for(int i=0; i<v[node].size(); i++){
		int next = v[node][i];
		if(check[next] == -1){
		check[next] = check[node] + 1;
        // 이전 정점의 정보를 from배열에 넣어줍니다.
		from[next] = node;
		q.push(next);
	}

그럼 어떻게 도착점에서 시작점까지 역추적하냐고요?
거꾸로, 뭔가 거꾸로할때는 스택을 이용합니다.

재귀를 사용해도 좋아요. 왜냐하면, 재귀가 내부적으로 스택으로 이루어져있기 때문입니다.

void tracing(int node){
    if(node == k) return;
    int next = from[node];
    tracing(next);
    printf("%d ", next);
}

바로 위의 문제의 출력 방법을 다음과 같이 바꿀께요.

출력 방법
1~n번까지 한줄씩 줄바꿈해서 시작점에서 해당 정점까지 도달하는데 거치는 정점을 공백으로 분리해서 출력하세요.
단, 방문할 수 없는 정점에 대해서는 -1을 출력하세요.
그리고, 시작점은 시작점 하나만 출력하세요

출력값

1
1 
1 
1 
1 2 
1 4 
1 
-1

C++

#include <iostream>
#include <vector>
#include <queue>
// 저는 보통 최대값 + 1을 매크로를 사용해서 선언해줍니다.
// 똑같은 숫자 반복사용하면 오타날때도 있고해서요
// 1증가 시키는 이유는 인덱스 참조하다가 실수 날 수 있어서
#define max_int 10001

using namespace std;

// 저는 보통 다음과 같이 4개의 정보를 주석으로 간단하게 작성해줍니다.
// 그냥, 내가 뭘 만들었는지는 알아먹을수 있어야해서요, 설명할 수는 있어야하잖아요

/*
 시간 복잡도: O(n+m)
 공간 복잡도: O(n)
 사용한 알고리즘: BFS(너비 우선 탐색)
 사용한 자료구조: 인접 리스트, 배열
 */

// check는 최단 거리를 저장할 배열입니다.
int n, m, k, a, b, check[max_int], from[max_int];

// 간선의 정보를 저장할 인접 리스트를 vector로 생성합니다.
vector<int> v[max_int];

// 너비 우선 탐색
void bfs(){
    // 큐를 만들어 줍니다.
    queue<int> q;
    // 시작점까지의 최단 거리는 0입니다.
    check[k] = 0;
    // 큐에 시작점을 넣어줍니다.
    q.push(k);
    
    // 큐가 비어있을때 까지 계속해줍니다.
    // 큐가 비었다는 의미는 시작점에 연결된 모든 다른 정점들을 방문했다는 의미입니다.
    while(!q.empty()){
        // 큐에서 가장 앞에있는것의 정보를 넣어줍니다.
        int node = q.front();
        // 큐 앞에 있는것 비워주는것 꼭 잊지말고요, 빼먹으면, 무한히 돌거에요
        q.pop();
        
        
        // 여기거 중요, 처음에는 낯설어요
        // 임의의 정점에서 연결되 다른 모든 정점들을 next에 넣습니다.
        for(int i=0; i<v[node].size(); i++){
            int next = v[node][i];
            
            // 만약 방문하지 않았다면
            if(check[next] == -1){
                // 여기도 중요! 반드시, 큐에 넣기 전에 방문했음을 체크해줍니다.
                // 여기서 체크안하면 다른 정점이 또 여기를 방문할 수 있습니다.
                // 문제의 예시에서 2 5, 3 5 인데, 2가 먼저 5를 방문했는데 표시 안해주면 3이 또 5를 큐에 넣습니다.
                
                // 간선을 타고 이동할때 마다 1 증가 시키기 때문에 이전 정점까지의 거리에 1을 더해줍니다.
                check[next] = check[node] + 1;
                // 이전 정점의 정보를 from배열에 넣어줍니다.
                from[next] = node;
                // 다음 정점을 큐에 넣어줍니다.
                q.push(next);
            }
        }
    }
}

void tracing(int node){
    if(node == k) return;
    int next = from[node];
    tracing(next);
    printf("%d ", next);
}

int main(){
    // 1. 입력
    // n 정점의 수, m 간선의 수, k 시작점의 번호를 입력 받습니다.
    scanf("%d %d %d", &n, &m, &k);
    
    // 2. 초기화
    // 거리 정보를 저장할 check 배열을 -1로 초기화합니다.
    // 무엇으로 초기화 할지는 개인의 취향입니다.
    for(int i=0; i<=n; i++) check[i] = -1;
    
    // 3. 간선 저장
    for(int i=0; i<m; i++){
        // 간선의 정보를 입력받고
        scanf("%d %d", &a, &b);
        // 중요, 무 방향그래프를 양방향 그래프로 만들어줍니다.
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    // 4. 너비 우선 탐색 수행
    bfs();
    
    // 5. 출력
    for(int i=1; i<=n; i++){
        // 1) 시작점인 경우
        if(i == k){
            printf("%d\n", i);
        }
        // 2) 시작점이 아닌 경우
        else{
            // 방문 할 수 있는 경우
            if(check[i] != -1){
                tracing(i);
                printf("\n");
            }
            // 방문 할 수 없는 경우
            else{
                printf("%d\n", -1);
            }
        }
    }
}

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static final int max_int = 10001;
    static int n, m, k, a, b;
    static int[] check = new int[max_int];
    static int[] from = new int[max_int];
    static ArrayList<Integer> v[] = new ArrayList[max_int];

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++) {
            check[i] = -1;
            v[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            v[a].add(b);
            v[b].add(a);
        }

        bfs();

        for(int i=1; i<=n; i++){
            // 1) 시작점인 경우
            if(i == k){
                System.out.println(i);
            }
            // 2) 시작점이 아닌 경우
            else{
                // 방문 할 수 있는 경우
                if(check[i] != -1){
                    tracing(i);
                    System.out.println();
                }
                // 방문 할 수 없는 경우
                else{
                    System.out.println("-1");
                }
            }
        }
    }

    public static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        check[k] = 0;
        q.add(k);

        while(!q.isEmpty()){
            int node = q.poll();

            for(int i=0; i<v[node].size(); i++){
                int next = v[node].get(i);

                if(check[next] == -1){
                    check[next] = check[node] + 1;
                    from[next] = node;
                    q.add(next);
                }
            }
        }
    }

    public static void tracing(int node){
        if(node == k) return;
        int next = from[node];
        tracing(next);
        System.out.print(next + " ");
    }
}

코드 팁

다음과 같은 정보를 저장하기 위해 배열을 2개 사용하는 경우가 있어요

1) 어떤 점을 방문 했음을 저장하기 위한 bool 배열
2) 어떤 점까지의 최단 거리를 저장하기 위한 int 배열

// 선언
bool visit[max_int];
int dist[max_int];

// 방문했을때
visit[next] = true;
dist[next] = dist[node] + 1;

사실, 2개를 동시에 사용할 필요가 없어요.
왜냐하면, 두 배열 모두 방문했음을 저장하기 때문에요.

dist 배열을 모두 -1로 초기화 했는데 어떤 정점(node)의 dist[node] 가 -1 이라면, 그 정점은 아직 방문하지 않은 정점이기 때문입니다.

같은 정보를 2개의 공간에 저장할 필요는 없기 때문에. 저는 다음과 같이 작성합니다. (갠취)

1) 방문 여부만 알고 싶을 때 (거리 구할 필요없음!)

// 선언
bool check[max_int]

// 방문했을때
if(!check[next]){
  check[next] = true;
}

2) 정점까지의 거리가 필요할때

// 선언
int check[max_int]

// 초기화
// BFS에서 최단 거리가 음수가 나올 수 없기 때문에 -1로 초기화
for(int i=0; i<=n; i++) check[i] = -1;

// 방문했을때
if(check[next] == -1){
  check[next] = check[node] + 1;
}

6. 주입식 정리

1) 정의
BFS는 시작점에서 인접한 정점을 모두 방문하고, 인접한 정점들에 대해서도 인점한 또 다른 정점을 방문하는 방법입니다.

BFS는 모든 정점과 간선을 방문하는 완전탐색입니다.

2) 최단 경로
BFS는 간선의 가중치가 모두 1인 그래프에서 최단 경로를 찾습니다.

3) 인접 정점 방문
인접 정점을 방문하기 위해서 자료구조 큐를 사용합니다.

큐는 먼저 들어간 요소가 먼저 나오는 구조입니다.

현재 정점과 인접한 모든 정점을 큐에 넣고, 다 넣으면 큐 앞에서 새로운 정점을 꺼내서 인접한 정점을 큐에 넣는 작업을 계속합니다.

시작점과 연결된 모든 정점을 넣을 때 까지.

4) 그래프 저장
그래프를 저장한다는 의미는 간선을 저장한다는 의미입니다.

그래프를 저장하는데는 2가지 방법이 있습니다.
인접 리스트 - 링크드 리스트 사용해서 구현
인접 행렬 - 2차원 배열 사용해서 구현

5) 시간 복잡도
인접 리스트 - 시간 복잡도는 O(V+E) 입니다. (V는 정점의 수, E는 간선의 수)
인접 행열 - 시간 복잡도는 O(v^2) 입니다. (V는 정점의 수)

6) 경로 추적
시작점에서 도착점 까지 경로를 추적할 수 있습니다.
다음 정점을 방문했을때 이전 정점을 저장하면 됩니다.

저장한 내용을 꺼내는 방법에는 스택이 있는데, 재귀를 사용해도 좋습니다. 왜냐하면, 재귀는 내부적으로 스택을 사용하기 때문입니다.

(여담으로, DP도 경로 추적할 수 있어요. 왜냐하면, 최종 문제를 풀려면 이전 문제를 반드시 풀어야 하기 때문입니다.)

7. 풀면 이해하는데 도움이 되는 문제

1. 백준 5567 결혼식
   1) 자신의 친구(최단 거리 1), 2) 자신의 친구의 친구 (최단 거리 2) 인 사람들의 수를 계산하는 문제입니다. 할 수 있어요!!

2. 백준 1389 케빈 베이컨의 6단계 법칙
   케빈 베이컨 게임 설명, 이 이야기를 중학교때 들었는데 BFS로 탐색 할 수 있었네요. 그리고, 케빈 베이컨은 엑스맨 퍼스트 클래스에서 인상 깊게 봤어요

3. 백준 2178 미로 탐색
   2차원 배열에서 BFS탐색 하는 방법을 알아봅시다.

2차원 배열이고 x, y에서 인접한 4방향(위, 아래, 왼쪽, 오른쪽)으로 1만큼 떨어진 칸을 방문하는 방법은 다음과 같습니다.

// dx, dy는 방향벡터라고도 부릅니다.
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};

// x, y중 딱 한개가 1만큼 변합니다.
for(int i=0; i<4; i++){
	int nx = x + dx[i];
    int ny = y + dy[i];
}

그래프 모델링을 위해 특별히 간선을 저장할 필요는 없습니다.

4. 백준 7576 토마토
   시작점이 여러개이면, 큐에 시작점을 다 넣어줍시다.

5. 코드포스 520B
   문제 발번역
   그래프 같지 않은 그래프 문제
   BFS에서 최단경로의 의미는 여러가지 입니다. 이 문제에서 최소 클릭수가 최단 경로가 됩니다.

6. 백준 9019 DSLR
   그래프 같지 않은 문제 이면서 동시에, 경로를 추적하는 문제입니다.

7. 백준 1726 로봇
   BFS와 DP를 함께 사용하는 방법입니다.
   방문을 표시하는 배열을 다음과 같이 사용합니다.

// check에는 x, y 좌표를 방문했고, 그때의 방향이 dir일때의 최단 거리를 저장해줍니다.
int check[x][y][dir];

8. 백준 16236 아기상어
   BFS를 사용해서 현재 아기상어의 위치에서 모든 물고기까지의 최단 경로를 구합니다.
   내풀이