[백준] 2206번 벽 부수고 이동하기

벽 부수는 것을 처음에 너무 간단하게만 생각했다가 여러번 틀린 문제입니다.

queue에 넣는 조건을 잘 나누지 않으면 메모리 초과가 나오기 십상이니 

명확하게 구분해야만 해결할 수 있는 문제였습니다.

 

먼저, 현재 좌표의 방문 여부를 벽을 부순적이 있는 경우와 없는 경우로 나눠서 진행해야 합니다. 

안그러면 아래 예시와 같은 경우에 -1이 나오게 됩니다.

4 4

0000

0 1 1 1

00 1 1

00 10

한번 방문해서 실패했다고 무조건 visited를 true로 바꿔주면..! 아래처럼 되버려서 실패하고 맙니다.

(0,0)->(0,1)->(1,1)->(2,1)->(3,1) 경로로 이동해서 한번 실패했다면, 해당 경로는 전부 visited = true가 되버립니다. 그러면,

(0,0)->(1,0)->(2,0)->(2,1) 의 경로의 경우 막혀버리게 되고

(0,0)->(1,0)->(2,0)->(3,0)->(3,1)의 경로 또한 막혀버리게 됩니다.

그래서 원치않는 -1 값이 나오게 됩니다..

 

그래서 두 경우로 나눠보면, 아래와 같습니다.

1. 벽 부순 횟수가 0이면서 해당 좌표에 방문한적이 없는 경우

    1-1) 해당 좌표에 벽이 없고 이전까지 벽 부순 횟수도 0 일경우

2. 벽 부순 횟수가 1이면서 해당 좌표에 방문한적이 없는 경우

    2-1) 해당 좌표에 벽이 있고 벽 부순 횟수가 0일 경우 

    2-2) 해당 좌표에 벽이 없고 벽 부순 횟수가 1일 경우

 

아래는 이를 토대로 작성한 코드입니다.

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int map[1000][1000];
bool visited[1000][1000][2] = { false };
int xpos[] = { -1,0,1,0 };
int ypos[] = {0, 1, 0, -1};
class Point{
public:
    int x;
    int y;
    int cnt;
    int brk;
    Point(int x, int y, int brk, int cnt) {
        this->x = x;
        this->y = y;
        this->cnt = cnt;
        this->brk = brk;
    }
};
int bfs(int n, int m) {
    queue<Point> q;
    q.push(Point(0,0,0,1));
    visited[0][0][0] = true;
    visited[0][0][1] = true;
    while (!q.empty()) {
        Point cur = q.front();
        q.pop();
        if (cur.x == n-1 && cur.y == m-1) {
            return cur.cnt;
        }
        for (int i = 0; i < sizeof(xpos) / sizeof(int); i++) {
            int nx = cur.x + xpos[i];
            int ny = cur.y + ypos[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                // 벽 부순 횟수가 0이면서 해당 좌표에 방문한적이 없는 경우
                if (!visited[nx][ny][0]) {
                    // 해당 좌표에 벽이 없고 이전까지 벽 부순 횟수도 0 일경우에만 push
                    if (map[nx][ny] == 0 && cur.brk == 0) {
                        q.push(Point(nx, ny, 0, cur.cnt + 1));
                        visited[nx][ny][0] = true;
                    }
                }
                // 벽 부순 횟수가 1이면서 해당 좌표에 방문한적이 없는 경우
                if (!visited[nx][ny][1]) {
                    // 해당 좌표에 벽이 있고 벽 부순 횟수가 0일 경우 
                    // or 해당 좌표에 벽이 없고 벽 부순 횟수가 1일 경우
                    if ((map[nx][ny] == 1 && cur.brk == 0) || (map[nx][ny] == 0 && cur.brk == 1)) {
                        q.push(Point(nx, ny, 1, cur.cnt + 1));
                        visited[nx][ny][1] = true;
                    }
                }
            }
        }
    }
    return -1;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        for (int j = 0; j < m; j++)
            map[i][j] = tmp[j] - '0';
    }
 
    cout << bfs(n,m);
    return 0;
}

 

코드에 문제가 있거나 더 나은 방법이 있는 경우엔 댓글 부탁드립니다 :)