너비 우선 탐색(BFS)

그래프 순회

저번에 배운 깊이 우선 탐색(Depth First Search)

- 스택을 이용하여 그래프를 순회하는 방법

 

너비 우선 탐색(Breadth First Search)

- 큐를 이용하여 그래프를 순회하는 방법

 

너비 우선 탐색(BFS)

인접한 노드들을 우선 모두 색칠해 두고 뻗어나간다.

위의 그림에서 너비 우선 탐색을 사용한다고 하자. 

우선 1을 큐에 넣고, (1)을 제거한다. -> 현재 노드 위치

1의 인접 노드인 2와 4를 큐에 넣는다.

이후 1의 이웃한 노드들이 모두 색칠되었으므로, 큐의 제일 앞 노드를 제거한다.(2)

2가 제거되었으므로 현재 노드 위치는 2이다. 2의 인접 노드인 3을 큐에 넣는다.

4는 이미 추가되어있으므로 추가하지 않음. 2의 인접 노드가 모두 색칠되었으므로, 큐의 제일 앞 노드를 제거(4)

4가 제거되었으므로, 현재 노드 위치는 4이다. 4의 인접 노드가 모두 색칠되어있으므로,  큐의 제일 앞 노드를 제거(3)

현재 노드 위치는 3이 된다. 3의 인접 노드 중 색칠되지 않은 5, 6, 7을 차례대로 큐에 넣는다.

큐에서 가장 앞인 5를 제거, 현재 위치는 5이다. 5의 인접 노드가 모두 색칠되었으므로 5도 제거(5)

큐의 가장 앞인 6을 제거, 현재 위치는 6, 6의 인접 노드가 모두 색칠되었으므로 6도 제거(6)

큐의 마지막 남은 (7)도 제거. 7의 인접 노드가 모두 색칠되었고, 큐도 비었으므로 종료

위의 순서대로 동작하게 된다. 

 

 

다음은 좀 더 심화된 그래프이다.

위에서 본 동작 과정대로 진행하게 된다면 위의 그림과 같은 결과가 나온다.

 

 

BFS 구현

첫 시작 정점이 0이라고 가정하고, 노드를 방문할 때는 노드 번호가 작은 순서대로 방문한다고 가정하자.

import java.util.*;

//너비우선탐색
public class Main {
    static int n;
    static int m;
    static List<Integer>[] myGraph;

    static boolean[] check;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        myGraph = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            myGraph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            myGraph[a].add(b);
            myGraph[b].add(a);
        }
        check = new boolean[n+1];
        BFS(0);
    }
    static void BFS(int x){
        //시작점을 큐에 넣음, 시작점을 색칠
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);
        check[x] =true;

        while (!queue.isEmpty()){
            int current = queue.poll();

            System.out.print(current+" ");

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

                if (check[next] == false){
                    check[next] = true;
                    queue.offer(next);
                }
            }
        }
    }
}

인접 리스트를 활용하여 구현하였다.

시작점이 0으로 가정하였기 때문에, 큐에 0을 넣고 재방문을 방지하기 위해 check [0] = true로 하였다.

BFS는 큐가 비게 된다면, 종료하게 된다.

 위에서 알아본 동작 과정대로 알고리즘이 작성되어 있다.

인접한 노드들 중 작은 노드부터 방문하지 않았다면, 큐에 넣게 된다.

이후 큐의 제일 앞부분을 제거하고, 그 부분이 다시 시작점이 된다.

 

 

 

BFS활용 문제를 풀어보자

 

2 색칠하기

위 문제는 단순하게 인접한 노드와 현재의 노드의 색깔을 다르게 칠한다는 것이다. 만약 이것이 가능하면 YES, 불가능하다면 NO를 출력한다.

import java.util.*;

public class Main {
    static int n;
    static int m;
    static List<Integer>[] graph;

    static boolean result = true;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        graph = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }

        BFS(0);
        System.out.println(result?"YES":"NO");
    }

    static void BFS(int x) {
        Queue<Integer> queue = new LinkedList<>();
        int[] color = new int[n + 1];
        queue.offer(x);
        color[x] = 1;

        while (!queue.isEmpty()) {
            int next = queue.poll();

            for (int i = 0; i < graph[next].size(); i++) {
                int v = graph[next].get(i);
                if (color[v] == 0){
                    if (color[next]==1)
                        color[v] = 2;
                    else if (color[next]==2)
                        color[v] =1;
                    queue.offer(v);
                }
                if (color[v]>0&&color[v]==color[next])result = false;
            }
        }
    }

}

이번 문제도 인접 리스트를 사용하였다. 

중요한 점은 앞서 말했지만, List를 배열 단위로 설정할 시 각각을 초기화해줘야 한다는 것이다.

이 문제에서는 방문 여부를 boolean타입이 아닌 int값으로 나타내었다.

만약 방문하지 않은 노드의 경우 초기값인 0을 가지고 있고, 현재 노드가 1이면 인접 노드는 2를 색칠하고,

현재 노드가 2이면 인접 노드에 1을 색칠한다. 

만약 현재의 노드와 인접 노드의 색깔이 같다면 NO가 된다. 

 

 

이상한 계산기

처음 이문제를 접했을 때, BFS를 어떻게 적용할지 고민하였다. 

점점 퍼져나가는 모양으로 우리가 만들어 가야 한다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Main {
    static int[] count;
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        count = new int[100000];

        bfs(1);
        System.out.println(count[n] - 1);
    }

    static void bfs(int x) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        count[x] = x;

        while (!queue.isEmpty()) {
            int next = queue.poll();

            int mul = next * 2;
            int div = next / 3;

            if (0 < mul && mul <= 99999) {
                if (count[mul] == 0) {
                    queue.offer(mul);
                    count[mul] = count[next] + 1;
                } else count[mul] = Math.min(count[mul], count[next] + 1);
                if (mul == n) break;
            }
            if (0 < div && div <= 99999) {
                if (count[div] == 0) {
                    queue.offer(div);
                    count[div] = count[next] + 1;
                } else count[div] = Math.min(count[div], count[next] + 1);
                if (div == n) break;
            }
        }
    }
}

이 문제에서 배열에는 카운트 값이 저장된다. 

위와 같은 모양으로 퍼져나가게 된다.

위 그림을 보면 count [mul] = Math.min(count [mul], count [next]+1)이 이해가 될 것이다.

값이 중복되는 경우가 생기기 때문에, 더 작은 카운트를 저장한다.

 

 

미로 찾기

4개의 방향으로 이동하는 이러한 문제는 dy, dx배열을 만들어서 풀면 코드가 짧아진다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n;
    static int m;
    static int[][] map;
    static int[][] check;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        check = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        bfs(n - 1, 0);
        System.out.println(check[0][m-1]);
    }

    static void bfs(int y, int x) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{y, x});
        check[y][x] = 0;
        while (!queue.isEmpty()) {
            int[] next = queue.poll();

            for (int i = 0; i < 4; i++) {
                int moveY = next[0] + dy[i];
                int moveX = next[1] + dx[i];

                if (0<=moveY&&moveY<n &&0<=moveX&&moveX<m){
                    if (map[moveY][moveX] == 0 &&check[moveY][moveX] ==0){
                        queue.offer(new int[]{moveY,moveX});
                        check[moveY][moveX] = check[next[0]][next[1]]+1;
                    }
                }
            }
        }

    }
}

이문제는 앞서 말했듯이 dy, dx 배열을 선언하여 반복문을 통해 코드를 간단하게 작성할 수 있다.

이전까지의 문제들은 큐 값에 1가지 값만 넣어도 풀 수 있었다.

하지만 이번 문제는 x, y값을 넣어야 하기 때문에 큐를 2개를 사용하거나, 큐에 배열을 넣어야 한다.

이번에는 배열을 넣어 사용하였다.

코드는 생각보다 단순하다. 4가지 방향으로 이동하는데, 방문하지 않았고, 벽이 아니라면 그 방향을 큐에 넣는다.

check는 카운트를 세는 용도와 방문 여부를 확인하기 위해 사용하였다.

따라서 이동한 check 값은 이동하기 전의 check 값보다 1이 작다. 

 

 

배운 점

DFS보다 동작 과정이 복잡하여 BFS가 초반에는 어렵게 느껴졌다.

하지만 공부하다 보니 재미있고, 이해할 수 있었다. 

마지막 문제의 경우에 처음 풀었을 때, 큐를 2개를 사용하여 풀었었다.

배열을 이용하여 코드가 더 간결해지게 되었다.

또한 4가지 방향을 갈 때 배열을 선언하지 않고 직접 각 방향을 작성하였는데, 

이러한 방법을 사용하니 중간중간 헷갈리고, 실수하는 부분이 생기게 되었다.

알고리즘을 많이 풀면서 방법이나 풀이에 익숙해져야겠다.