벽 부수고 이동하기 2 14442

문제

접근 방법

벽 부수고 이동하기의 원리와 같다. 3차원 배열에 1번 부순 경우, 안 부순 경우로 나뉘는 것 대신 K번 부순 경우까지를 구현하면 되는 것이다.

코드

#include <iostream>
#include <string>
#include <queue>
using namespace std;
#define MAXSIZE 1000
struct node
{
    int y, x, cnt, wall;
};
int dy[] = {1, -1, 0, 0}, dx[] = {0, 0, 1, -1};
bool visted[11][MAXSIZE][MAXSIZE], wall[MAXSIZE][MAXSIZE];
queue<node> bfs;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, K;
    cin >> N >> M >> K;
    for (int i = 0; i < N; ++i)
    {
        string line;
        cin >> line;
        for (int j = 0; j < M; ++j)
        {
            wall[i][j] = line[j] == '0' ? false : true;
        }
    }
    visted[0][0][0] = true;
    bfs.push({0, 0, 1, 0});
    while (!bfs.empty())
    {
        node cur = bfs.front();
        bfs.pop();
        if (cur.y == N - 1 && cur.x == M - 1)
        {
            cout << cur.cnt;
            return 0;
        }
        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 (wall[next.y][next.x])
            {
                if (next.wall < K && !visted[next.wall + 1][next.y][next.x])
                {
                    visted[next.wall + 1][next.y][next.x] = true;
                    bfs.push({next.y, next.x, next.cnt, next.wall + 1});
                }
            }
            else if (!wall[next.y][next.x] && !visted[next.wall][next.y][next.x])
            {
                visted[next.wall][next.y][next.x] = true;
                bfs.push(next);
            }
        }
    }
    cout << -1;
    return 0;
}

풀이

3차원 bool 배열이 아닌 2차원 int 배열을 사용한 방식도 있었다.
뚫은 벽의 수, 좌표, 거리를 저장해준 뒤 뚫어야 하면 뚫은 벽의 수를 늘려주고 방문했다고 표시해주면 된다.
BFS이기에 가장 먼저 목표지점에 도착한 경우가 가장 최단 경로임을 명심하면 된다.

시간, 메모리 초과가 났었다. 방문하고 true로 안 바꿔준 것, 크기가 1인 경우, 방문한 경우를 체크할 때는 현재가 아니라 미래의 때에 따라 처리해줘야 하는 것을 제대로 못 해서 틀렸다.