[Baekjoon] 백준 1261번 알고스팟

1261번 알고스팟 문제 풀이

문제

• 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NM 크기이며, 총 11크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.
  알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (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)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

예제

입력
3 3
011
111
110

4 2
0001
1000

6 6
001111
010000
001111
110001
011010
100010

출력
3

0

2

코드

deque 사용

#include<iostream>
#include<deque>
#include<cstdio>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;

int n, m;
int road[555][555];
int check[555][555];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int main() {
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &road[i][j]);
            check[i][j] = -1;
        }
    }
    deque<pair<int, int>> dq;
    check[0][0] = 0;
    dq.push_back(make_pair(0, 0));
    while (!dq.empty()) {
        int x = dq.front().first;
        int y = dq.front().second;
        dq.pop_front();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (check[nx][ny] == -1) {
                    if (road[nx][ny] == 0) {
                        check[nx][ny] = check[x][y];
                        dq.push_front(make_pair(nx, ny));
                    }
                    else {
                        check[nx][ny] = check[x][y] + 1;
                        dq.push_back(make_pair(nx, ny));
                    }
                }
            }
        }
    }
    cout << check[n-1][m-1] << "\n";
    return 0;
}

두 개의 queue 사용

#include<iostream>
#include<deque>
#include<cstdio>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;

int n, m;
int road[555][555];
int check[555][555];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int main() {
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &road[i][j]);
            check[i][j] = -1;
        }
    }
    deque<pair<int, int>> dq;
    check[0][0] = 0;
    dq.push_back(make_pair(0, 0));
    while (!dq.empty()) {
        int x = dq.front().first;
        int y = dq.front().second;
        dq.pop_front();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (check[nx][ny] == -1) {
                    if (road[nx][ny] == 0) {
                        check[nx][ny] = check[x][y];
                        dq.push_front(make_pair(nx, ny));
                    }
                    else {
                        check[nx][ny] = check[x][y] + 1;
                        dq.push_back(make_pair(nx, ny));
                    }
                }
            }
        }
    }
    cout << check[n-1][m-1] << "\n";
    return 0;
}

해결방법

deque 사용

• BFS탐색을 사용하여 부순 벽의 개수를 파악하게된다.
• 벽을 부쉈더니 길이 오픈되어있는 경우에는 우선적으로 탐색해야하기 때문에 deque를 사용하여 다음 경로를 queue의 front에 넣어준다.
• 벽이 있을 경우 부순 벽의 개수를 하나 증가시키며 queue의 end에 넣어준다.

• if (check[nx][ny] == -1) {
    if (road[nx][ny] == 0) {
        check[nx][ny] = check[x][y];
        dq.push_front(make_pair(nx, ny));
    }
    else {
        check[nx][ny] = check[x][y] + 1;
        dq.push_back(make_pair(nx, ny));
    }
  }

두 개의 queue 사용

• BFS탐색을 사용하는건 deque와 동일하다.
• 단지 q라고 명칭한 첫 번째 q에 우선탐색을 필요로 하는 데이터를 넣어주고, 그렇지 않은 경우는 next_q에 데이터를 넣어준다.

if (check[nx][ny] == -1) {
    if (road[nx][ny] == 0) {
        check[nx][ny] = check[x][y];
        q.push(make_pair(nx, ny));
    }
    else {
        check[nx][ny] = check[x][y] + 1;
        next_q.push(make_pair(nx, ny));
    }
}

• 우선 탐색하는 q가 비워지면 종료되기 때문에 q가 empty상태이며 next_q에는 데이터가 들어있는 경우에는 next_q의 데이터를 q로 옮겨주며 next_q를 비워준다.

  if (q.empty()) {
    q = next_q;
    next_q = queue<pair<int, int>>();
  }