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

문제링크 : https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M;
int arr[1001][1001];
bool visited[1001][1001][2]; //0 : 벽 안부숨, 1 : 벽 부숨
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

struct info{
    int y, x, depth, wall;
};

int bfs()
{
    queue<info>q;
    q.push({0, 0, 1, 0});
    visited[0][0][0]=1;

    while(!q.empty())
    {
        auto[y, x, depth, wall] = q.front();
        q.pop();

        if(x == M-1 && y == N-1) return depth; //목표 지점 도달

        for(int i=0; i<4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(nx < 0 || ny < 0 || nx >=M || ny >=N) continue;
            if(arr[ny][nx] && !wall) //벽인데 아직 안부숨
            {
                visited[ny][nx][1] = 1;
                q.push({ny, nx, depth+1, 1});
            }
            if(!arr[ny][nx] && !visited[ny][nx][wall]) //갈 수 있는데, 아직 안감
            {
                visited[ny][nx][wall] = 1;
                q.push({ny, nx, depth+1, wall});
            }
        }
    }
    return -1; //목표 지점 도달 불가
}
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    cin >> N >> M;

    for(int i=0; i<N; i++)
    {
        string s;
        cin >> s;
        for(int j=0; j<M; j++)
        {
            arr[i][j] = s[j]-'0';
        }
    }

    cout << bfs();
    
    return 0;
}

bfs의 응용문제이다.

먼저 큐에 들어갈 값이 많아서 구조체로 선언하고 시작했다. (y좌표, x좌표, 경로, 벽 부숨 유무)

그리고 해당 좌표가 목표 좌표에 도달하면 여태 더해준 경로를 출력하고, 도달이 불가하다면 -1을 출력한다.

 

bfs 내부를 보면 크게 벽인데 아직 안부쉈을 때와 갈 수 있는데 아직 안 갔을 때 이렇게 2가지가 있다.

현재 벽인데 아직 안부쉈다면, 벽이 부숴졌다는 것을 표시해주고 경로를 더해준다.

이후 아래 조건문에서 앞으로 갈 수 있는 경로에 대해서 탐색을 이어나가게 된다.

 

따라서 위에 있는 조건문으로 벽을 1개씩 부순 경로를 큐에 넣고, 아래 조건문을 통해서 위에서 벽을 부순 경로를 이어받아서 탐색하게 된다.

이렇게 모든 벽에 대해서 하나씩 부수면서 어떤 거리가 가장 짧은 지를 저장해나간다.

 

해당 문제에서 주의해야할 것이 있는데 바로 입력부분이다.

나는 별생각없이 바로 arr[i][j]을 입력받았는데 입력 부분을 보면 숫자 사이에 간격이 없다.

이는 한줄당 문자열로 입력받아서 이를 다시 숫자로 바꿔서 받아야 하는 것을 의미한다.

이를 나중에 알아서 처음에 값이 이상하게 나오는 바람에 잘못푼줄 알고 다소 헤맸다.

 

만약 그냥 arr[i][j]을 입력받으려면 입력 간격을 하나씩 띄워놓으면 맞게 나오는 것을 볼 수 있다.

다른 사람 풀이를 보는데 왜 굳이 문자열로 입력받나 했었는데 이런 이유였다.

애초에 N의 범위가 1000이라서 int arr[i][j]로 입력받는 것이 불가하다.

이를 고려하지 않아서 이또한 늦게 알았다.