[백준 1261, c++] 알고스팟(bfs,deque)

문제 번호

• 1261(https://www.acmicpc.net/problem/1261)

문제 및 입/출력

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.

(1, 1)과 (N, M)은 항상 뚫려있다.

 

출력

첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

 

예제 입력1

3 3 011 111 110

예제 출력1

3

예제 입력2

4 2 0001 1000

예제 출력2

0

예제 입력3

6 6 001111 010000 001111 110001 011010 100010

예제 출력3

2

 

문제 풀이

N*M 크기의 미로에서 시작점 (1,1) 에서 도착점(N,M) 까지 이동하는데 부셔야하는 최소 벽 개수를 구하는 문제이다. 방금전 BOJ 13549(숨바꼭질3)의 문제를 풀고와가지고 그런지 쉽게 풀 수 있었다.

 

• 최소의 벽을 부시고 목적지까지 가는것이 목표이기때문에 우선은 이동이 가능하다면 목적지에 가깝게 최대한 이동해야한다. 즉, 우선순위가 이동가능한 칸(0)을 가는 것이 높게된다.
• 이 문제는 단순한 BFS를 요구하는 문제가 아니다. 왜냐하면 BFS는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문이다.
• 그렇기 때문에 이 문제는 다음과 같은 방법들을 사용하여 해결할 수 있다.
  • 다익스트라 알고리즘
  • BFS 가중치가 0(우선순위가 높은)인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법
• 보통 이 문제는 다익스트라 알고리즘을 이용하여 푸는게 정석인거 같지만, 우선 이번 글에서는 deque를 이용하여 우선순위를 구분해 푸는 두번째 방법으로 풀어보겠다.

 

파랑 - 출발점, 빨강 - 도착점, 회색 - 벽, 하얀색 - 이동가능한 칸

1. 미로의 크기 및 미로 정보를 입력받는다.
2. 시작점 1,1에서부터 상하좌우로 탐색을 진행하며 deque를 이용하여 조건 1(맵을 벗어나지 않고, 갈 수있는 길(=0)이고, 방문하지 않았다면)이라면 deque의 맨앞에 삽입하고, 조건2(맵을 벗어나지 않고, 갈 수없는 길(=1)이고, 방문하지 않았다면)이라면 deque의 맨 뒤에 삽입한다.
3. deque의 앞에서부터 빼서 사용하므로 우선순위는 조건1 > 조건2가 된다.
4. 조건1일때는 visited 함수의 값은 default 값인 1로 유지가 되며, 조건2일때는 벽을 부시는 것이므로 +1씩 증가하게 된다.
5. 목적지 (N,M)에 도착할때까지 탐색을 이어나가고 도착한다면 bfs 함수에서 반환된 visited[N][M] - 1을 출력한다.

* -1을 하는 이유는 default 가 1에서부터 시작했기 때문이다.

소스 코드

#include <iostream>
#include <deque>
#include <stdio.h>
#include <cstring> // memset
 
using namespace std;
 
#define MAX 100
 
struct component {
    int y, x;
};
 
// 우,하,좌,상
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
 
int M, N;
bool graph[MAX+1][MAX+1];
int visited[MAX+1][MAX+1];
 
bool is_inside(int ny, int nx){
    return (ny >= 1 && ny <= N && nx >= 1 && nx <= M);
}
 
int bfs() {
    deque<component> dq;
    dq.push_back({ 1, 1 });
    visited[1][1] = 1;
    while (!dq.empty()) {
        int y = dq.front().y;
        int x = dq.front().x;
        dq.pop_front();
 
        if (y == N && x == M) return visited[N][M] - 1;
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            // 맵을 벗어나지 않고, 갈 수있는 길이고, 방문하지 않았다면
            if (is_inside(ny,nx) && graph[ny][nx] == 0 && visited[ny][nx] == 0) {
                dq.push_front({ ny,nx });
                visited[ny][nx] = visited[y][x];
            }
 
            // 맵을 벗어나지 않고, 갈 수없는 길이고, 방문하지 않았다면
            if (is_inside(ny, nx) && graph[ny][nx] == 1 && visited[ny][nx] == 0) {
                dq.push_back({ ny,nx });
                visited[ny][nx] = visited[y][x] + 1;
            }
        }
    }
}
 
int main() {
    /* 미로의 크기 및 미로 정보 입력*/
    scanf("%d %d", &M, &N);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%1d", &graph[i][j]);
        }
    }
 
    /* BFS 탐색 및 결과 출력 */
    printf("%d\n", bfs());
    return 0;
}