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

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

2206번: 벽 부수고 이동하기

정답률 20프로대의 난이도가 있는 문제였다.

이 문제 역시 BFS 문제였지만, 벽을 한 번 부술 수 있다는 조건이 추가되었기 때문에 생각하기 어려웠던 것 같다.

 

1. 풀이 방법 및 논리

 

일반적으로 BFS로 최단거리를 구할 때는 visited[y][x]를 bool 배열로 선언하여 방문여부의 유무를 표현하였다.

그러나 이 문제에서 visited[y][x][power]는 거리 정보를 넣고, 추가로 power이라는 요소를 추가하였는데, 여기서 power는 "y, x 좌표로 오는동안 벽을 부수었는지를 체크하는 값" 을 의미한다. 만약 power가 1이라면 벽을 한 번도 부수지 않았고, 한 번 부술 수 있는 힘이 있다는 뜻이고, 만약 power가 0이라면 이미 벽을 한 번 부수고 왔기 때문에 앞으로는 벽을 부술 수 없다는 의미이다. 

 

시작 시에는 벽을 부수지 않은 상태이고, 부술 수 있는 힘이 남아있기 때문에, BFS 큐에 {{0, 0}, 1} 을 push 해준다.

그 후, BFS를 수행하다가 만약 좌표가 (N - 1, M - 1)에 도달하게 된다면 visited 배열에 저장되어 있는 거리 값을 return 해주면 된다.

 

만약 큐가 비워질 때까지 마지막 점(N - 1, M - 1)까지 도달하지 못한다면, 이는 해당 좌표까지의 이동이 불가능한 상태이기 때문에 -1을 return 해주는 방식으로 소스코드를 짰다.

 

2. 소스코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 1001;
int N, M;
int map[MAX][MAX];
int visited[MAX][MAX][2];
int dy[] = { 0, 0, -1, 1 };
int dx[] = { -1, 1, 0, 0 };

int BFS() {
    queue<pair<pair<int, int>, int>> q;
    q.push({{0, 0}, 1}); // 큐에 시작 위치 좌표 0,0 과 벽을 부술 수 있다는 의미의 1을 넣어줌
    visited[0][0][1] = 1;

    while(!q.empty()) {
        pair<pair<int, int>, int> p = q.front();
        q.pop();

        if (p.first.first == N - 1 && p.first.second == M - 1)
            return visited[N-1][M-1][p.second];

        for (int i = 0; i < 4; i++) {
            int ny = p.first.first + dy[i];
            int nx = p.first.second + dx[i];
            int power = p.second;

            if (nx < 0 || ny < 0 || nx >= M || ny >= N || visited[ny][nx][power])
                continue;
            if (power && map[ny][nx] == 1) {
                q.push({{ny, nx}, power - 1});
                visited[ny][nx][power-1] = visited[p.first.first][p.first.second][power] + 1;
            }
            if (map[ny][nx] == 0) {
                q.push({{ny, nx}, power});
                visited[ny][nx][power] = visited[p.first.first][p.first.second][power] + 1;
            }
        }
    }
    return -1;
}

int main() {
    string input;
    cin >> N >> M;

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

    cout << BFS() << endl;
}

 

제출 결과 (2번 째 시도 끝에 통과)