2206번

2206번 - 벽 부수고 이동하기

기본적인 BFS에 한차원을 더 늘려서 문제를 풀면 된다.

어떤 지점에 도달했을 때, 벽을 하나 부수고 이동한 상태인지/ 벽을 부수지 않고 이동한 상태인지 를 나눴다.

dist[x][y][0] 은 x,y 좌표에 도달했을 때 벽을 부수지 않고 도달한 경우, 

dist[x][y][1] 은 x,y 좌표에 도달했을 때 벽을 한번 부수고 도달한 경우

이를 이용해서 큐에 값을 넣을 때

벽을 부술 수 있는지? -> 벽인지/벽이 아닌지 + 방문한적이 있는지? -> 계산해서 큐에 넣기

이런과정을 통해서 문제를 해결할 수 있다.

<정답 코드>

#include<iostream>
#include<queue>
using namespace std;
int n, m;
int ans = -1;
int map[1001][1001];
int dist[1001][1001][2];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char tmp;
            cin >> tmp;
            map[i][j] = tmp - '0';
        }
    }
 
    queue < pair<int, pair<int, int>>> q;
    dist[1][1][0] = 1;
    q.push({ 0,{ 1,1 } });
 
    while (!q.empty())
    {
        int x = q.front().second.first;
        int y = q.front().second.second;
        int c = q.front().first;
 
        if (x == n && y == m)
        {
            cout << dist[x][y][c] << "\n";
            return 0;
        }
 
        q.pop();
 
        for (int d = 0; d < 4; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if (nx >= 1 && ny >= 1 && nx <= n && ny <= m)
            {
                if (c == 0)
                {
                    if (map[nx][ny] == 1 && dist[nx][ny][1] == 0)
                    {
                        dist[nx][ny][c + 1] = dist[x][y][c] + 1;
                        q.push({ c + 1,{ nx,ny } });
                    }
                    else if (map[nx][ny] == 0 && dist[nx][ny][c] == 0)
                    {
                        dist[nx][ny][c] = dist[x][y][c] + 1;
                        q.push({ c,{ nx,ny } });
                    }
                }
                else if (c == 1)
                {
                    if (map[nx][ny] == 0 && dist[nx][ny][1] == 0)
                    {
                        dist[nx][ny][c] = dist[x][y][c] + 1;
                        q.push({ c,{ nx,ny } });
                    }
 
                }
 
            }
        }
    }
 
 
    cout << "-1\n";
    
 
    return 0;
}