[백준 2206] 벽 부수고 이동하기

문제 출처: https://www.acmicpc.net/problem/2206

풀이

공주님을 구해라! https://www.acmicpc.net/problem/17836 와 비슷한 문제로, 3차원배열을 이용하여 풀었습니다.

문제가 똑같아보여서 출력하는것만 수정하고(시작점과 도착점도 시간포함) 제출했는데 틀렸습니다. 

공주님 문제는 검을 얻으면 도착할 때 까지 벽(1)을 빈칸(0)으로 간주할 수 있지만, 이 문제는 벽을 안부시거나 딱 한번만 부시기 때문에 

벽을부순 이후와 검을 먹은 이후의 시뮬레이션의 차이가 있으므로 어느정도 수정해야했습니다.

3차원 배열은 벽을 부시지않았을때(0), 벽을 부셨을 때(1)를 표현하기위해 선언하였고 4가지 경우에대해서만 구현하면됩니다.

실제로는 2가지만 구현하면됩니다.

1. 벽을 만났는데 벽을 부순적이없다.

->벽을 뚫었는지를 나타내는 get변수(0:뚫지않았음 1:뚫었음)를 1로 바꿔서 벽을 뚫었다고 표현해주고, 벽을 부순자리의 visited값을 벽 부수기 직전자리의 visited값+1으로 수정시킵니다. 이 때 visited[ny][nx][get]=visited[y][x][get]+1으로 선언하면  현재 벽을 부수지않고 도착한 좌표를 직전자릿값+1으로 바꾼다고도 볼수 있으므로, 

벽을 부수고 도착한 좌표임을 나타내기위해 visited[ny][nx][get+1]=visited[y][x][get]+1로 선언합니다.

2. 빈 칸을 만났는데 방문하지않은곳이다.

직전 좌표값 +1 처리해줍니다. visited[ny][nx][get]=visited[y][x][get]+1 해줍니다. 

1번 처리로 인해 벽을 부순좌표에서 넘어온것과 벽을 부수지않은 좌표에서 넘어온것이 구분됩니다.

3. 벽을 만났는데 벽을 부순적이있다.

-> 어떠한 연산도 하지않고 넘어갑니다. (continue or 분기)

4. 빈 칸을 만났는데 방문한적이 있는곳이다.

-> 어떠한 연산도 하지않고 넘어갑니다. (continue or 분기)

마지막으로 모든 연산 후 큐가 비었음에도 도착좌표에 도착하지않았다면 도착이 불가능함을 의미하므로 -1을 출력합니다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int n, m,visited[1000][1000][2], ans;
char temp[1000][1000];
int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
int map[1000][1000];
void bfs(int y, int x,int get);
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin >> n>> m;
    for (int i = 0; i < n; i++)
    {
        cin >> temp[i];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            map[i][j] = temp[i][j] - '0';
        }
    }
    
    bfs(0, 0,0);
}
void bfs(int y, int x, int get)
{
    queue<pair<pair<int, int>, int>>q;
    q.push({ {y,x},get });
    visited[y][x][get] = 1;
 
    while (!q.empty())
    {
        y = q.front().first.first;
        x = q.front().first.second;
        get = q.front().second;
        q.pop();
        if (y == n - 1 && x == m - 1)
        {
            cout << visited[y][x][get] <<'\n';
            return;
        }
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny >= 0 && nx >= 0 && ny < n && nx < m)
            {
                //벽을 만났는데 벽을 뿌신적이없다면
                if (map[ny][nx] == 1&&get==0)
                {
                    visited[ny][nx][get + 1] = visited[y][x][get] + 1;
                    q.push({ {ny,nx},get + 1 });
                }
                    //벽이없고 방문하지않은곳이면 
                else if(map[ny][nx]==0&&visited[ny][nx][get]==0)
                {
                    visited[ny][nx][get] = visited[y][x][get] + 1;
                    q.push({ {ny,nx},get });
                }
            }
        }
    }
    cout << -1 << '\n';
    return;
}

결과