[Baekjoon, Gold 3] 벽 부수고 이동하기

 

2206번: 벽 부수고 이동하기

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define X first
#define Y second
#define endl '\n'

vector<vector<int>> direction = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

vector<string> MakeMatrix()
{
    int width, height;
    cin >> width >> height;

    vector<string> matrix(width);

    for (size_t i = 0; i < matrix.size(); ++i)
    {
        string path;
        cin >> path;

        matrix[i] = path;
    }

    return matrix;
}

void BFS(vector<string>& Matrix, queue<pair<pair<int, int>, pair<int, bool>>>& q, vector<vector<bool>>& visited)
{
    while (!q.empty())
    {
        int cx = q.front().first.X; // 현재 X좌표
        int cy = q.front().first.Y; // 현재 Y좌표

        if (cx == Matrix.size() - 1 and cy == Matrix[0].size() - 1)
        {
            cout << q.front().second.second << endl;

            return;
        }

        int dist = q.front().second.first; // 현재 좌표까지의 거리

        bool bBreak = q.front().second.second; // 벽을 부순 적 있는지

        q.pop();

        for (size_t i = 0; i < direction.size(); ++i)
        {
            int nx = cx + direction[i][0];
            int ny = cy + direction[i][1];

            // X 좌표가 범위 밖인지 체크
            if (0 > nx or nx >= Matrix.size()) continue;

            // Y 좌표가 범위 밖인지 체크
            if (0 > ny or ny >= Matrix[0].size()) continue;

            // 방문 한 적 있는지 (매트릭스 자체를 Visited로 체크)
            if (visited[nx][ny] == 1) continue;

            if (bBreak) // 벽을 아직 부수지 않았다면
            {
                if (Matrix[nx][ny] == '1') // 벽을 만났다면
                {
                    q.push({ {nx, ny}, {dist + 1, false} });

                    visited[nx][ny] = true;
                }
                else // 벽을 만나지 않았다면
                {
                    q.push({ {nx, ny}, {dist + 1, true} });

                    visited[nx][ny] = true;
                }
            }
            else // 벽을 부순 경우
            {
                if (Matrix[nx][ny] == '1') continue;

                q.push({ {nx, ny}, {dist + 1, bBreak} });

                visited[nx][ny] = true;
            }
        }
    }

    cout << -1 << endl; // 경로 없음
}

int main()
{
    vector<string> Matrix = MakeMatrix();

    queue<pair<pair<int, int>, pair<int, bool>>> q;
    // { Coord X, Coord Y}, { Distance, bBreak }
    q.push({ { 0, 0 }, { 1, true } });

    vector<vector<bool>> visited(Matrix.size(), vector<bool>(Matrix[0].size(), 0));
    visited[0][0] = true;

    BFS(Matrix, q, visited);

    return 0;
}

벽을 부순 경우와 안 부순 경우로 나누어 탐색해야 하는데, 현재 로직에서 한번 방문 하면, 재방문이 불가능
그러므로 부순 경우와 안 부순 경우를 다루어줄 Visited 배열이 하나 더 필요

---

최종 풀이 코드

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

#define X first
#define Y second
#define endl '\n'

const vector<pair<int, int>> direction = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

// 맵과 방문 배열
int N, M;
vector<string> map;
vector<vector<vector<int>>> visited;

// 맵 입력 처리
void Init()
{
    cin >> N >> M;

    visited.assign(N, vector<vector<int>>(M, vector<int>(2, 0)));

    map.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> map[i];
}

// 좌표가 맵 범위 내에 있는지 확인
bool IsValid(int cx, int cy)
{
    return 0 <= cx and cx < N and 0 <= cy and cy < M;
}

// BFS로 최단 경로 찾기
int BFS()
{
    // tuple: {cx, cy, broken, dist}
    queue<tuple<int, int, int, int>> q;
    q.emplace(0, 0, 0, 1); // 시작점: (0,0), 벽 안 부숨, 거리 1
    visited[0][0][0] = 1;

    while (!q.empty())
    {
        int cx, cy, broken, dist;
        tie(cx, cy, broken, dist) = q.front();
        q.pop();

        if (cx == N - 1 and cy == M - 1)
            return dist;

        for (const auto& d : direction)
        {
            int nx = cx + d.X; // 다음 X 좌표
            int ny = cy + d.Y; // 다음 Y 좌표

            if (!IsValid(nx, ny)) continue;

            // 벽이 아닌 경우
            if (map[nx][ny] == '0' and !visited[nx][ny][broken])
            {
                visited[nx][ny][broken] = 1;
                q.emplace(nx, ny, broken, dist + 1);
            }
            // 벽을 만났고, 아직 부수지 않은 경우
            else if (map[nx][ny] == '1' and broken == 0 and !visited[nx][ny][1])
            {
                visited[nx][ny][1] = 1;
                q.emplace(nx, ny, 1, dist + 1);
            }
        }
    }

    return -1; // 경로 없음
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    Init();

    int result = BFS();

    cout << result << endl;

    return 0;
}

벽을 부순 경우, 안 부순 경우로 나누어 탐색할 수 있도록, Visited배열을 3차원 배열로 설정하여 Broken 관리