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

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

 

문제 링크

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

문제 내용

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

 

 

Idea

NxM의 행렬로 표현되는 맵

• 0 : 이동할 수 있는 곳
• 1 : 이동할 수 없는 곳

단순히 벽을 피해 이동하는 최단 경로를 구하라고 하면 간단한 bfs구현만으로 가능하다. 그러나 벽을 한 개 까지 부수고 이동할 수 있다는 점이 새로운 규칙이 되었다.

어떠한 지점에 벽을 부수고 가거나 부수고 가지 않더라도 최단 경로가 같다면 이런 경우를 어떻게 해결해야 할까. 보통 bfs에서 방문 표시(visit)를 하기 위해서는 2차원 배열을 사용하지만, 이 문제에서는 벽을 부수었는지에 따른 여부를 알기 위해 3차원 배열로 만든다.  또한, 큐의 매개변수에도 wall을 추가해준다. 이는 구조체를 활용하였다.

• visit[x][y][wall]
• visit[x][y][0] : 벽을 부수지 않고 좌표(x, y)를 방문
• visit[x][y][1] : 벽을 부수고 좌표(x, y)를 방문

 

다음은 bfs의 조건에 대해 알아보자.

• 지금껏 가던 경로 중 벽을 부순 적이 없으면서 벽과 마주할 때(line 46 ~ line 51)
• 벽이 아닐 때(line 52 ~ line 57)

벽을 위한 배열을 만들어 주었다면 쉽게 풀만한 문제였다. (자세하진 않지만...) 코드 설명은 주석으로 넣어뒀다. 그리고 이 문제 풀이 방법에 대해 제대로 이해했다면 아래 문제도 풀어보길 추천한다! 끝!

 

※추천 문제※

백준 1600 : 말이 되고픈 원숭이

(비슷한 유형의 bfs)

 

 

Code

#include <stdio.h>
#include <queue>
using namespace std;
 
typedef struct {
    int x;
    int y;
    int wall;
}st;
 
int map[1001][1001];
int result[1001][1001];
bool visit[1001][1001][2];
 
int main() {
    int N, M;
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
 
 
    queue<st> q;
    q.push({ 1,1,0 });
    visit[0][0][0] = visit[0][0][1] = true;
    result[1][1] = 1;
 
    int dx[] = { 1,-1,0,0 };
    int dy[] = { 0,0,1,-1 };
 
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int wall = q.front().wall;
        q.pop();
 
        //이동하기
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx > 0 && ny > 0 && nx <= N && ny <= M) {
                //벽이고 부순적이 없으면서 방문안한곳 
                if (map[nx][ny] == 1 && wall == 0 && !visit[nx][ny][wall + 1]) {
                    visit[nx][ny][wall + 1] = true;
                    result[nx][ny] = result[x][y] + 1;
                    q.push({ nx,ny,wall + 1 });
                }
                //벽이 아니고 방문 안한곳
                if (map[nx][ny] != 1 && !visit[nx][ny][wall]) {
                    visit[nx][ny][wall] = true;
                    result[nx][ny] = result[x][y] + 1;
                    q.push({ nx,ny,wall });
                }
                //목표에 도착했을 경우
                if (nx == N && ny == M) {
                    printf("%d\n", result[nx][ny]);
                    return 0;
                }
            }
        }
 
    }
 
    /*목표에 도착하지 못했을 경우*/
    if (N == 1 && M == 1) printf("1\n");
    else printf("-1\n");
 
    return 0;
}