백준 2206번 - 벽 부수고 이동하기 (C++)

문제

해결 방법

일반적이지 않은 최단거리 문제라 BFS를 이용하여 구현하였으며,

visit를 3차원 배열로 선언하여서 [좌표][좌표][벽을 뚫고 여기까지 도착했는가?]를 표시하였다. [][][1] 이면 해당 좌표까지 도착하는 길에 벽을 뚫고 온 것이고 [][][0]이라면 해당 좌표까지 오는 길에 벽을 뚫고 오지 않은 것.

또한, queue에 좌표뿐 아니라 해당 경로에서 벽을 뚫고 왔는지에 대한 변수 또한 필요하여 총 3개의 변수를 이용하여 queue를 구성하였다.

아쉬웠던 점

없음

코드

#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
using namespace std;
 
pair<int, int> Dir[4] = { {0,1 },{1,0}, {-1,0}, {0,-1} };
int N, M, Visit[1001][1001][2] = { 0, 0, };
bool Map[1001][1001] = { 0, }; 
 
struct xyzw
{
    int x, y;
    bool z;
    xyzw(int a, int b, bool c) : x(a), y(b), z(c) { }
};
 
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            scanf("%1d", &Map[i][j]);
 
    if (N == M && N == 1)
    {
        cout << "1";
        return 0;
    }
 
    queue<xyzw> Que;
    Que.push({0, 0, 0});
    Visit[0][0][0] = 1;
 
 
    while (!Que.empty())
    {
        xyzw Xy = Que.front();
        Que.pop();
        
        for (int i = 0; i < 4; ++i)
        {
            int _X = Xy.x + Dir[i].first;
            int _Y = Xy.y + Dir[i].second;
            if (_X >= 0 && _X < N && _Y >= 0 && _Y < M)
            {
                if (Map[_X][_Y] == 0 && !Visit[_X][_Y][Xy.z])
                {
                    Visit[_X][_Y][Xy.z] = Visit[Xy.x][Xy.y][Xy.z]+1;
 
                    if (_X == N - 1 && _Y == M - 1)
                    {
                        cout << (Visit[Xy.x][Xy.y][Xy.z] + 1);
                        return 0;
                    }
                    Que.push({ _X, _Y, Xy.z});
                }
                else if (!Xy.z && !Visit[_X][_Y][1] && !Visit[_X][_Y][0])
                {
                    Visit[_X][_Y][1] = Visit[Xy.x][Xy.y][Xy.z] + 1;
                    Que.push({ _X, _Y, 1});
                }
            }
        }
    }
 
    cout << "-1";
}

 

잡설 : vs컴파일은 scanf_s로 해야하고 코드 제출은 scanf로 해야해서 컴파일 오류로 정답률을 많이 깎아먹었다...ㅋㅋㅋㅋ 그리고 메모리가 정말 간당간당한 문제라서 조금이라도 경우의수가 많아지면 바로 메모리 초과가 걸리는 것 같다.