[c++] BOJ 2206 :: 벽 부수고 이동하기

난이도 : 골드 4

걸린 시간 : 오래 걸림

문제

벽 부수고 이동하기 문제 보러가기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

 

풀이

• 모든 경로를 살펴볼 필요없이 최단 경로를 구하면 되므로 bfs를 이용한다.
• 벽을 부수고 이동할 수 있으므로 벽을 부쉈는지의 여부까지 메모이제이션 해야한다.

 

코드

[dfs] => 틀린 코드

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int N, M;
int map[1001][1001];
int direction[4][2] = { {0,1},{-1,0},{0,-1},{1,0} };
int memo[1001][1001][2];

int shortestPath(bool brakeRemain, int r, int c) {
    if (r == N - 1 && c == M - 1)
        return 1;
    int minPath = 1e8;
    for (int i = 0; i < 4; i++) {
        int rp = r + direction[i][0];
        int cp = c + direction[i][1];
        int type = 0;

        if (rp < 0 || cp < 0 || rp >= N || cp >= M) // 맵 안에 없으면
            continue;
        if (brakeRemain)
            type = 1;

        int res;
        if (map[rp][cp] == 0) {
            if (memo[rp][cp][type] != -1)
                res = memo[rp][cp][type];
            else {
                memo[rp][cp][type] = 1e8;
                res = shortestPath(brakeRemain, rp, cp) + 1;
                memo[rp][cp][type] = res;
            }
            if (minPath > res)
                minPath = res;
        }
        else {
            // 벽이면
            if (!brakeRemain) // 부술 수 없으면 건너뛰기
                continue;
            if (memo[rp][cp][0] != -1) // 메모이제이션
                res = memo[rp][cp][0];
            else {
                memo[rp][cp][0] = 1e8; // 다시 되돌아오지 못하게
                res = shortestPath(!brakeRemain, rp, cp) + 1;
                memo[rp][cp][0] = res;
            }
            if (minPath > res)
                minPath = res;
        }
    }

    return minPath;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < str.size(); j++) {
            map[i][j] = str[j]-'0';
        }
    }
    memset(memo, -1, sizeof(memo));

    int res = shortestPath(true, 0, 0);
    if (res >= 1e8)
        res = -1;
    cout << res;

}

[bfs] => 성공 코드

#include <iostream>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

int N, M;
int map[1001][1001];
int direction[4][2] = { {0,1},{-1,0},{0,-1},{1,0} };
int memo[1001][1001][2];

struct Node {
    int r;
    int c;
    bool breakRemain = true;
    int p;
    Node(int row, int col, bool b) {
        r = row; c = col; breakRemain = b; p = 0;
    }
    Node(int row, int col, bool b, int path) {
        r = row; c = col; breakRemain= b; p = path;
    }
};

int main() {
    // 11시 40분 시작
    // 벽 하나는 부숴도 됨
    // 상하좌우 이동
    // 최단 경로
    // n,m 은 1000이하
    // 불가능 시 -1
    // 작은 문제 : 해당 칸에서 마지막까지의 최단 경로
    // 입력 : 지금까지 벽을 부순적이 있는지, 현재 칸
    // 출력 : 최단 경로
    // 메모이제이션 : 해당 칸, 벽 부숨 여부
    // 종료 : 마지막 칸에 도달, 더 갈곳이 없고 벽부숨도 없음

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < str.size(); j++) {
            map[i][j] = str[j]-'0';
        }
    }
    memset(memo, -1, sizeof(memo));

    queue<Node*> que;
    que.push(new Node(0, 0, true));
    memo[0][0][0] = 0;
    memo[0][0][1] = 0;

    int flag = 1;
    while (!que.empty()) {
        Node* node = que.front(); que.pop();
        int r = node->r; int c = node->c; bool b = node->breakRemain;
        int path = node->p +1;
        if (r == N - 1 && c == M - 1) {
            // 마지막 도착
            flag = 0;
            cout << path;
            break;
        }
        for (int i = 0; i < 4; i++) {
            int rp = r + direction[i][0];
            int cp = c + direction[i][1];
            if (rp < 0 || cp < 0 || rp >= N || cp >= M) // 맵 안에 없으면
                continue;
            if (memo[rp][cp][b ? 1 : 0] != -1) // 이미 했던 곳이면
                continue;

            if (map[rp][cp] == 0) {
                // 벽이 아니면
                que.push(new Node(rp, cp, b, path));
                memo[rp][cp][b ? 1 : 0] = path;
            }
            else {
                // 벽이면
                if (!b) // 벽부수기가 없으면
                    continue;
                que.push(new Node(rp, cp, false, path));
                memo[rp][cp][b ? 1 : 0] = path;
            }
        }
    }
    if (flag) {
        cout << -1;
    }
}

 

결과