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

 

[적용한 알고리즘]

BFS, DP(약간의 냄새가 남)

 

[아이디어]

벽만 안부수면 평범한 BFS 예제 문제인데, 

벽을 최대 한번만 부술 수 있으니까 그걸 적용시켜주는 것이 핵심이 될 것이다. 

1. 모든 벽을 한번씩 지워보고 각각의 경웨서 BFS를 돌리는 경우 -> 시간초과임

2. 벽을 부순 상태, 안부순 상태를 저장해 BFS를 이용하는 경우 -> 가능할듯?

 

[생각의 흐름 / 절차] 

대부분의 내용은 기존 BFS와 동일.

상태를 담아줘야하므로 (약간 dp같이) BFS에서 경우를 나눠서 저장해주면 되겠다.

 

[교훈]

1. tuple 꽤 유용 구조체 선언해줘도 되지만 이왕 있는거 써먹어도 괜찮을듯?

2. 상태를 저장해주는 거 꼭 기억하자. BFS나 DFS를 넘겨줄때는 항상 같은 상태로 넘겨줘야하므로,

아예 상태를 같이 넘겨주는 꼴이어야함.

 

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
#include <tuple>
#define size 1001
using namespace std;

int n, m;
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
int map[size][size];
int visited[size][size][2];
queue<tuple<int, int, int>> q;

bool inMap(int x, int y){
    if (1 <= x && x <= n && 1 <= y && y <= m) return true;
    return false;
}

int bfs(){
    //z = 0 이면 아직 벽을 한번도 안뚫은 상태
    //z = 1 이면 벽을 한 번 뚫은 상
    while (!q.empty()){
        int curx, cury, z;
        tie(curx, cury, z) = q.front();
        q.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inMap(nx, ny)){ // 다음에 방문할 곳이 map 안에 있다면
                if (map[nx][ny] == 0 && visited[nx][ny][z] == 0){
                    visited[nx][ny][z] = visited[curx][cury][z] + 1;
                    q.push({nx, ny, z});
                } // 다음 이동하는 곳에 벽이 없고, 아직 방문하지 않은 곳이라면

                if (z == 0 && map[nx][ny] == 1 && visited[nx][ny][1] == 0){
                    visited[nx][ny][1] = visited[curx][cury][0] + 1;
                    q.push({nx, ny, 1});
                } // 현재 벽을 부수지 않은 상태고, 다음에 갈 곳이 벽이고, 아직 방문하지 않은 상태라면
            }
        }
    }

    if (visited[n][m][0] * visited[n][m][1] != 0)
        return min(visited[n][m][0], visited[n][m][1]);
    // 벽을 뚤고 가지 않은 경우와 뚫고 간 경우 둘 다 가능하다면 작은 애를 리턴
    if (visited[n][m][0] != 0) return visited[n][m][0];
    if (visited[n][m][1] != 0) return visited[n][m][1];
    // 둘 중 하나만 가능하다면 가능한 애 리턴
    return -1; // 아니면 그냥 리턴
}
int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            scanf("%1d", &map[i][j]);
        }
    }

    q.push({1, 1, 0});
    visited[1][1][0] = 1;

    printf("%d\n", bfs());
    return 0;
}