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

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 너비우선 탐색(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;
}