본문 바로가기

Dev/Algorithm

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

반응형

www.acmicpc.net/problem/2206

 

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로

www.acmicpc.net

 너비우선 탐색(BFS)로 풀어야 하는 문제다. '벽을 최소 1회는 뚥을수 있다'는 조건이 문제를 어렵게 만드는데, 이부분은 벽을 최소 1회 뚥었는지, 안뚥었는지에 대한 조건 여부를 방문 여부에 차이를 두고 기록해야한다. 

#include <stdio.h>
#include <iostream>
using namespace std;
#include <queue>

typedef struct _loc {
    int y;
    int x;
    int distance;
    int wall_break;
}loc;

int N, M;
char map[1001][1001];
bool visited[2][1001][1001];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

int bfs() {
    loc start;
    start.y = 1;
    start.x = 1;
    start.distance = 1;
    start.wall_break = 0;
    visited[start.wall_break][start.y][start.x] = true;

    queue<loc> bfs_queue;
    bfs_queue.push(start);

    while(!bfs_queue.empty()){
        loc pop = bfs_queue.front();
        bfs_queue.pop();

        if(pop.y == N && pop.x == M) return pop.distance;
        
        for(int i=0; i<4; ++i){
            loc next;
            next.y = pop.y + dy[i];
            next.x = pop.x + dx[i];
            next.wall_break = pop.wall_break;
            next.distance = pop.distance + 1;
            if(next.y < 1 || next.y > N || next.x < 1 || next.x > M){
                continue;
            }
            if(visited[next.wall_break][next.y][next.x]){
                continue;
            }
            if(map[next.y][next.x] == '0'){
                visited[next.wall_break][next.y][next.x] = true;
                bfs_queue.push(next);
            }
            if(map[next.y][next.x] == '1' && next.wall_break == 0){
                next.wall_break = 1;
                visited[next.wall_break][next.y][next.x] = true;
                bfs_queue.push(next);
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d%d", &N, &M);
    for(int i=1; i<=N; ++i) {
        char temp[1001];
        scanf("%s", temp);
        for(int j=1; j<=M; ++j){
            map[i][j] = temp[j-1];
        }
    }

    printf("%d\n", bfs());

    return 0;
}
반응형