벽 부수고 이동하기 2206

문제

첫 번째 접근 방법

벽을 '한번' 부수고 간다면 Bool을 추가하여 BFS를 돌려주면 된다고 생각했다.

첫 번째 실패

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <climits>
using namespace std;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
struct node
{
    int y, x, cnt;
    bool wall;
};
int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<bool>> isVisted = vector<vector<bool>>(N, vector<bool>(M));
    vector<vector<bool>> wall = vector<vector<bool>>(N, vector<bool>(M));
    queue<node> bfs;
    for (int i = 0; i < N; ++i)
    {
        string line;
        cin >> line;
        for (int j = 0; j < M; ++j)
        {
            wall[i][j] = (line[j] == '1' ? true : false);
        }
    }
    bfs.push({0, 0, 1, false});
    while (!bfs.empty())
    {
        node cur = bfs.front();
        cout << cur.y << " " << cur.x << " " << cur.wall << " " << cur.cnt << "\n";
        if (cur.y == N - 1 && cur.x == M - 1)
        {
            break;
        }
        bfs.pop();
        for (int i = 0; i < 4; ++i)
        {
            node next = {cur.y + dy[i], cur.x + dx[i], cur.cnt + 1, cur.wall};
            if (next.y < 0 || next.x < 0 || next.y >= N || next.x >= M)
                continue;
            if (isVisted[next.y][next.x])
                continue;
            isVisted[next.y][next.x] = true;
            if (wall[next.y][next.x])
            {
                if (!next.wall)
                    bfs.push({next.y, next.x, next.cnt, true});
            }
            else
                bfs.push(next);
        }
    }
    if (bfs.empty())
        cout << -1;
    else
        cout << bfs.front().cnt;
    return 0;
}

실패했다.

공간	벽	공간	공간	공간	벽	공간
공간	벽	공간	벽	공간	벽	공간
공간	공간	공간	벽	공간	벽	공간

이런 식의 형태라면 돌아가야 하지만 바로 벽을 뚫기에 isVisted을 true로 만들고 못 돌아가게 한다.
그렇다면 어떻게 해야 할까?
벽을 부수는 경우와 같이 사용하는 isVisted이 평범한 길을 망치니 나눠주면 될 것 같다.

두 번째 접근 방법

그렇다. isVisted의 차원을 3차원으로 하자.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <climits>
using namespace std;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
struct node
{
    int y, x, cnt;
    bool wall;
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<vector<vector<bool>>> isVisted = vector<vector<vector<bool>>>(2, vector<vector<bool>>(N, vector<bool>(M)));
    vector<vector<bool>> wall = vector<vector<bool>>(N, vector<bool>(M));
    queue<node> bfs;
    for (int i = 0; i < N; ++i)
    {
        string line;
        cin >> line;
        for (int j = 0; j < M; ++j)
        {
            wall[i][j] = (line[j] == '1' ? true : false);
        }
    }
    bfs.push({0, 0, 1, false});
    while (!bfs.empty())
    {
        node cur = bfs.front();
        if (cur.y == N - 1 && cur.x == M - 1)
        {
            break;
        }
        bfs.pop();
        for (int i = 0; i < 4; ++i)
        {
            node next = {cur.y + dy[i], cur.x + dx[i], cur.cnt + 1, cur.wall};
            if (next.y < 0 || next.x < 0 || next.y >= N || next.x >= M)
                continue;
            if (isVisted[cur.wall][next.y][next.x])
                continue;
            isVisted[cur.wall][next.y][next.x] = true;
            if (wall[next.y][next.x])
            {
                if (!next.wall)
                    bfs.push({next.y, next.x, next.cnt, true});
            }
            else
                bfs.push(next);
        }
    }
    if (bfs.empty())
        cout << -1;
    else
        cout << bfs.front().cnt;
    return 0;
}

풀이

실패한 경우에 적어둔 내용과 동일하다. 평범하게 돌다가 벽을 만나면 벽을 만나면 벽을 부수고 돈다. 하지만 isVisted는 기존의 도는 것과 겹치는 영역이 아니다. 각자의 isVisted으로 이미 방문했는지를 체크해주는 것이다.

제출하고 시간을 확인했을 때 (cin, cout tie해주는 거를 안 해서 추가하고 다시 돌렸을 때) 44ms라는 생각보다 짧은 시간이 나와서 놀랐다. 그래서 맞힌 사람 순위를 확인해보니, 내가 19등이었다. 진짜 놀랐다. 우연인 것 같고 금방 내려올 순위일 것 같아서 일단 캡처해서 기념으로 올린다.