[Algorithm] 0-1 BFS 알고리즘(격자그래프 편) with Java

0-1 BFS 알고리즘

 

들어가며

이 글은 아래의 0-1 BFS(인접 리스트 편)과 이어지는 내용입니다. 여기선 격자 그래프에서 0-1 BFS 알고리즘을 구현하는 방법만 다루기 때문에 0-1 BFS 알고리즘을 알고 싶은 분은 아래의 링크에 들어가서 먼저 읽어보고 오는 것을 추천드립니다.

[Algorithm] 0-1 BFS 알고리즘(인접 리스트 편) with Java

 

 

---

 

 

격자 그래프에서 0-1 BFS 문제 정의

우선 격자 그래프가 어떻게 주어져야 0-1 BFS 알고리즘을 적용할 수 있을 지 생각해보아야합니다.

아래의 그림을 보겠습니다.

0-1 BFS 알고리즘을 적용하기 위한 예제

 

현재 몬스터가 존재하는 셀을 지나면 체력이 1 소모 된다고 가정하겠습니다. 또한 상하좌우로 한 번에 최대 1칸씩 이동할 수 있을 때 start에서 end지점까지 도달하기 위한 최소한의 체력 소모를 구하는 문제입니다. 즉, 몬스터가 존재하는 셀을 최대한 지나지 않고 end까지 도달하는 것이 목표입니다.

 

 

사람의 풀이

먼저 컴퓨터가 아닌 사람의 눈으로 풀어보겠습니다.

사람이 문제를 풀었을 때 해법

 

그림을 보면 적어도 2마리의 몬스터를 지나야 end 지점까지 도달할 수 있는 것을 알 수 있습니다. (다른 경로도 가능)

 

 

컴퓨터의 풀이

이제 컴퓨터의 관점에서 생각해보겠습니다.

컴퓨터는 사람처럼 한 번에 최소한의 비용으로 목표 지점까지 도달하는 방법을 찾을 수가 없습니다. 대신 비용이 들지 않는 셀부터 BFS 알고리즘으로 방문해보면서 현재 칸이 목표 지점이라면 탐색을 종료하고, 목표 지점이 아니라면 현재 셀과 인접한 셀 중 비용이 들지 않는 셀을 우선으로 찾아봐야합니다. 그리고 인접한 셀 중에 몬스터가 존재하는 셀이 있다면 해당 셀의 우선순위는 가장 마지막이 됩니다.

 

정리하면

1. 현재 칸이 목표 지점인지 확인
2. 목표 지점이 아닌 경우 인접한 셀 탐색
3. 인접한 셀로 이동할 때 비용이 들지 않는다면 우선적으로 탐색
4. 인접한 셀로 이동할 때 비용이 든다면 후순위로 탐색
5. 목표 지점을 찾을 때까지 반복

정점과 간선으로 나타낸 인접 리스트와 특별히 다른 내용은 없기 때문에 쉽게 이해할 수 있을거라 생각합니다.

 

 

그림으로 보는 0-1 BFS

앞선 예시인 그림을 다시 가져와서 어떤 방식으로 0-1 BFS가 진행되는 지 알아보겠습니다.

용이한 표현을 위해 각 셀에 2차원 좌표가 아닌 1부터 49까지 번호를 붙였습니다.

또한, 초기에 각 셀에 이동하기 위한 최소 비용은 INF 값으로 초기화 되어있습니다.

 

 

i) 1번 셀에서 인접한 셀 탐색

시작점인 1번 셀에서 인접한 셀은 2번과 8번 셀입니다.

2번 셀은 몬스터가 존재하므로 덱의 뒤쪽에 삽입하고, 8번 셀은 비어있으므로 덱의 앞쪽에 삽입합니다.

그리고 2번 셀은 몬스터가 존재하므로 비용을 1 증가시킨 상태로 삽입해야합니다.

 

아래는 모두 삽입한 뒤의 덱 상태입니다.

 

ii) 덱에서 8번 셀 하나 꺼내서 다시 탐색

게시글 상단의 글을 먼저 읽고 왔다면 알겠지만 0-1 BFS 알고리즘은 자료구조에 셀을 추가하는 순간에 방문 확정을 지을 수 없습니다. 나중에 접하게 될 셀 중에 얼마든지 비용이 더 낮은 경우도 존재할 수 있기 때문입니다. 대신 덱의 앞에서 추출한 셀은 최소비용임이 보장됩니다. 따라서 덱에서 추출할 때마다 확정되었다는 의미로 해당 셀의 위치를 분홍색으로 색칠하겠습니다.

 

1번 셀에서 2번 셀로 이동하려면 체력이 1 소모되기 때문에 빨갛게 1을 적어줬습니다. 또한, 8번 셀로 이동할 땐 체력이 들지 않기 때문에 0을 적었습니다.

 

8번 셀과 인접한 셀 중 방문하지 않은 15번 셀을 덱의 앞에, 9번 셀을 덱의 뒤에 삽입합니다.

그 후 덱은 아래와 같습니다.

 

iii) 덱에서 15번 셀 하나 꺼내서 다시 탐색

반복되는 설명은 생략하겠습니다.

이제 덱에서 15번 셀을 꺼내 최소 비용들을 갱신하고, 인접한 셀을 다시 덱에 넣겠습니다.

 

22번 셀과 16번 셀은 덱의 앞에 추가됩니다.

 

iv) 비용이 0인 셀 모두 탐색

비용이 0인 셀을 가능한 전부 방문해보면 격자그래프와 덱은 아래와 같게 변하게 됩니다.

이제 덱 안에 들어있는 셀은 전부 1의 비용을 가지고 있습니다.

 

v) 비용이 1인 2번 셀 추출 및 인접한 셀 탐색

처음으로 비용이 1인 2번 셀을 꺼냈습니다.

2번 셀은 아직 확정되지 않은 3번과 9번 셀을 탐색할 수 있는데 2번 셀에서 9번 셀로 이동하면 최소비용이 2가 됩니다. 따라서 기존에 저장된 +1보다 크기 때문에 굳이 선택할 이유가 없습니다.

결국 3번 셀만 덱의 앞쪽에 추가됩니다.

 

vi) 3번 셀부터 시작해 다시 비용이 0인 셀 전부 탐색

3번 셀을 추출하면 결국 iv 케이스처럼 인접한 빈 칸들을 전부 방문하게 됩니다.

이때, 각 셀로 이동하기 위한 최소비용은 1이라는 점을 주의해야합니다.

또한, 빈 셀들의 인접한 칸을 덱에 추가하면서 이제 비용이 2인 셀도 생겼습니다.

 

vii) 9번, 17번 셀은 더이상 탐색할 인접한 셀이 없음

이제 덱의 앞을 추출하면 9번 셀인데 9번 셀의 상하좌우는 이미 최소비용이 확정됐습니다.

또한, 17번 셀도 더이상 진행할 방향이 존재하지 않습니다.

따라서 9번, 17번 셀은 비용이 1로 확정되고 바로 다음 과정으로 넘어갑니다.

 

viii) 24번 셀 추출 및 인접한 셀 탐색

이제 24번 셀을 추출했습니다. 이번에도 마찬가지로 빈 셀을 전부 탐색해보겠습니다.

24번 셀과 인접한 31번 셀부터 시작해 비어있는 셀 전부 최소비용 1로 확정 지었습니다.

 

그리고 덱의 상황은 아래와 같습니다.

 

ix) 30번 셀은 더이상 탐색할 셀이 없음

덱의 앞에서 추출한 30번 셀은 vii처럼 더이상 진행할 방향이 존재하지 않습니다. 아래인 37번 셀로 이동하려면 체력이 총 2가 소모되므로 굳이 탐색할 필요가 없기 때문입니다.

따라서 30번 셀의 비용을 1로 확정하고, 다음 과정으로 넘어갑니다.

 

x) 36번 셀을 추출하고 빈 칸 전부 탐색

이제 덱에서 36번 셀을 추출합니다. 36번 셀의 상하좌우를 보면 43번 셀과 37번 셀이 확정되지 않은 것을 알 수 있습니다. 37번 셀로 이동할 필요는 없기 때문에 43번 셀을 덱의 앞에 삽입합니다.

그렇게 되면 덱에서 다시 43번 셀을 추출하고, 이어서 44번 셀까지 최소비용이 1이 되는 것을 알 수 있습니다.

 

아래는 현재 덱의 상태입니다.

 

xi) 6번 셀을 추출하고 7번, 14번 셀까지 확정

이제 어떤 방식으로 진행되는지 감이 왔을테니 더 빠르게 진행해보겠습니다.

 

이젠 덱에서 6번 셀을 꺼내서 최소비용 2를 확정 짓고, 오른쪽의 7번 셀까지 확정 짓습니다.

이어서 14번 셀까지 확정 짓겠습니다.

 

xii) 21번 셀을 추출하고 비어있는 셀 전부 탐색

21번 셀을 꺼내서 인접한 셀을 탐색해보면 아래 방향으로 진행할 수 있습니다. 28번 셀을 포함해 목표 지점까지 전부 비어있는 셀입니다.

결과적으로 목표 지점까지 도달하기 위한 최소한의 비용은 2임을 알 수 있습니다. 이는 우리가 눈으로 풀었을 때와 동일한 결과입니다.

 

xiii) 덱에 남아있는 셀은 전부 생략

남은 셀들은 전부 추출하면 최종적인 최소비용을 알 수 있습니다.

 

 

0-1 BFS 실제 구현 코드 : 격자그래프

앞선 예시 문제에 대해 자바 코드로 구현하겠습니다. 

최종 목표는 49번 셀까지의 최소비용이지만 모든 셀에 대한 최소비용으로 구해보겠습니다.

 

BFS 및 0-1 BFS 인접리스트 편의 코드와 매우 유사해서 중요한 부분만 주석으로 설명했습니다.

public class Main_01_BFS_Grid {
    static final int INF = 100000000;

    static int row, col;
    static int[][] matrix;
    static int cost[][];

    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        row = Integer.parseInt(st.nextToken()); // 행
        col = Integer.parseInt(st.nextToken()); // 열

        // 배열 초기화
        matrix = new int[row][col];
        cost = new int[row][col];
        for(int i = 0; i < row; i++) {
            // 비용 배열 무한대로 초기화
            Arrays.fill(cost[i], INF);

            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < col; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 출발 지점 입력
        st = new StringTokenizer(br.readLine(), " ");
        int sx = Integer.parseInt(st.nextToken());
        int sy = Integer.parseInt(st.nextToken());

        zobfs(sx, sy);

        // 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                sb.append(cost[i][j]);
                if(j < col-1) sb.append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb.toString().trim());
    }

    private static void zobfs(int x1, int y1) {
        Deque<int[]> deq = new ArrayDeque<>();

        deq.offer(new int[] {x1, y1, 0});
        cost[x1][y1] = 0;

        while(!deq.isEmpty()) {
            int[] poll = deq.poll();

            // 상하좌우 탐색
            for(int delta = 0; delta < 4; delta++) {
                int nx = poll[0] + dx[delta];
                int ny = poll[1] + dy[delta];

                // 범위 체크 및 비용 감소 체크
                if(nx >= 0 && ny >= 0 && nx < row && ny < col && cost[nx][ny] > poll[2] + matrix[nx][ny]) {
                    if(matrix[nx][ny] == 0) {
                        deq.offerFirst(new int[] {nx, ny, poll[2]});
                        cost[nx][ny] = poll[2];
                    } else {
                        // matrix[nx][ny] == 1이면 몬스터 존재하므로 비용 1 증가
                        deq.offerLast(new int[] {nx, ny, poll[2]+1});
                        cost[nx][ny] = poll[2] + 1;
                    }
                }
            }
        }
    }
}

입력
7 7
0 1 0 0 0 1 0
0 1 0 0 0 0 1
0 0 1 0 1 0 1
0 0 1 1 0 1 0
0 1 0 0 0 1 0
1 1 0 1 1 0 0
0 0 1 1 0 0 0
0 0

출력
0 1 1 1 1 2 2
0 1 1 1 1 1 2
0 0 1 1 2 1 2
0 0 1 2 1 2 2
0 1 1 1 1 2 2
1 2 1 2 2 2 2
1 1 2 3 2 2 2

 

출력과 위의 그림을 비교해보면 일치하는 것을 볼 수 있습니다.

 

 

.

.

.

 

 

마치며

긴 글 읽어주셔서 감사합니다. 0-1 BFS는 역시 격자그래프가 더 재밌습니다!!

끝으로 0-1 BFS 알고리즘을 연습하기 좋은 문제를 백준에서 추천드립니다.

• 2665 미로 만들기 : https://www.acmicpc.net/problem/2665
• 1261 알고스팟 : https://www.acmicpc.net/problem/1261 (미로 만들기와 유사)
• 23563 벽 타기 : https://www.acmicpc.net/problem/23563

궁금한 점이나 글에 대한 피드백은 댓글로 부탁드립니다. 😊