[BOJ] C++ 2206 벽 부수고 이동하기 - BFS 활용

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

예제

6 4
0100
1110
1000
0000
0111
0000

15

4 4
0111
1111
1111
1110

ans : -1

---

처음에는 BFS를 하는데, dist를 pair로 해서 방문가능하지 판단할 때 if(dist.second) >= 2 continue; 이런 느낌으로 한 번 부수면 계속 그 사실을 기억하는 식으로 풀이를 짰다. 그러나 pair로 구현하면 구현이 굉장히 복잡해지고 많은 최적화가 필요했다. 따라서 간단하게 dist 2차원 배열을 3차원 배열로 만들어서 dist [][][0]은 벽을 부수지 않고 도달한 최단 거리, dist [][][1]은 벽을 부수고 도달한 최단 거리로 구성하여 dist [][][1]로 bfs를 돌리다가 벽을 만나면 continue 하는 식으로 해결했다. 오히려 너무 어렵게 생각하면 풀기 어려운 문제였다.

/** BFS 2206 벽 부수고 이동하기 **/
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#define MAX 1002
using namespace std;

string board[MAX];
int dist[MAX][MAX][2]; // dist[x][y][0]은 벽을 부수지 않았을 때 (x, y)까지의 dist이다.

int n, m;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

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

    /* 초기화 부분 */
    cin >> n >> m;
    queue<pair<pair<int, int>, int>> Q;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            dist[i][j][0] = dist[i][j][1] = -1;

    for (int i = 0; i < n; i++)
    {
        cin >> board[i];
    }

    dist[0][0][0] = dist[0][0][1] = 1;
    Q.push(make_pair(make_pair(0, 0), 0));
    /******************************************************************************************************/

    while (!Q.empty())
    {
        pair<int, int> cur = Q.front().first;
        int flag = Q.front().second;
        if (cur.first == n - 1 && cur.second == m - 1)
        {
            cout << dist[n - 1][m - 1][flag];
            return 0;
        }
        Q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            //(nx, ny)는 cur의 상하좌우 칸이다.
            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if (dist[nx][ny][flag] >= 0)
                continue;
            if (board[nx][ny] == '1')
            {
                if (flag)
                    continue;
                else
                {
                    // 벽을 부순 경우
                    dist[nx][ny][1] = dist[cur.first][cur.second][flag] + 1;
                    Q.push(make_pair(make_pair(nx, ny), 1));
                }
            }
            else
            {
                // 벽이 아닌 경우
                dist[nx][ny][flag] = dist[cur.first][cur.second][flag] + 1;
                Q.push(make_pair(make_pair(nx, ny), flag));
            }
        }
    }
    cout << -1;
}