[BOJ-2206]벽부수고이동하기

http://acmicpc.net/problem/2206

[풀이방법]

*주의 처음위치와 마지막 위치도 최단거리로 포함한다.

두가지 방법으로 풀이를 해보았다.

1. 총 R x C 의 지도에서 벽을 한번씩 제거한 후 [시작위치, 도착위치] 로 가게 하여 BFS 를 진행하는 경우.
2. BFS로 처음부터 끝까지 가는 경우. [가능한 벽부시기 횟수][ROW][COL]

1번 방법으로는 전형적인 BFS방법으로 탐색을 진행한다. 정말 시간초과 몇번 받아보고 어거지로 풀려고 노력을 했다. 

다른 분들은 1초가 넘지 않는 시간으로 풀이를 진행하여 2번방법을 진행했다. 사설이 길었다. 

BFS() : 시작위치부터 도착위치까지의 최단거리

1번 방법은 말 그대로 문하나를 까고 BFS()를 진행한 후 문하나를 다시 위치에 설치한다.

아주 무식한 방법이었다. 

완전탐색은 완전탐색인데 시간초과를 받아서 가지치기를 진행하였다. 

가지치기 진행방법은 하나를 지우고 상하좌우에 벽이 그대로 남아있다면? 벽을 제거해도 소용이 없는 경우이다. 그렇기 때문에 이 경우는 다음 벽을 부신다.

이와 같이 진행한다. 

2번 방법으로는 BFS방법이다. 

[가능한 벽부시기 횟수][ROW][COL] 로 진행을 한다. 

처음 [0][0] 위치에서는 가능한 벽부시기 횟수가 1이다. 

그렇기 때문에 [1][0][0] 에 1을 저장한다. 

만약 벽이 [1][0] 위치에 있다면? 벽을 부시면서 [0][1][0]에 값을 갱신하고, 큐에 pos(0,1,0) // pos(r, c, breaker) 을 넣어주면 된다.

이후 진행은 동일하므로 생략한다. 

그리고 마지막 위치에 값과 ans 값을 비교한다. 만약 마지막 위치에 도달한 값이 -1인 경우. 도달할 수 없으므로 continue 하여 ans 값을 갱신시킬수없게 하였다. 

마지막 결과를 출력할 때 ans가 INF 이라면? 도달 할 수 없는 경우이다. 

[C++11]

#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
 
const int dr[] = { 0,0,-1,1 };
const int dc[] = { -1,1,0,0 };
const int m = 1111;
const int INF = 1 << 22;
 
char im[m][m];
int vis[m][m];
int row, col;
 
struct pos {
    int r, c;
    pos(int ir, int ic) : r(ir), c(ic) {}
};
int main() {
    scanf("%d%d", &row, &col);
    for (int r = 0; r < row; r++) {
        scanf("%s", im[r]);
    } // input
 
    int ans = INF;
 
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            if (im[r][c] == '0') continue;
            int n_wall = 0;
            int check_wall = 4;
            for (int i = 0; i < 4; i++) {
                int tr = r + dr[i];
                int tc = c + dc[i];
                if (tr < 0 || row <= tr || tc < 0 || col <= tc) {
                    check_wall--;
                    continue;
                }
                if (im[tr][tc] == '1') n_wall++;
            } // check wall
            if (n_wall == check_wall) continue;
 
            memset(vis, -1, sizeof(vis));
            im[r][c] = '0';
            queue<pos> Q = queue<pos>();
            Q.push(pos(0, 0));
            vis[0][0] = 1;
            bool is_over_ans = false;
            while (!Q.empty()) {
                pos here = Q.front(); Q.pop();
                int hr = here.r;
                int hc = here.c;
 
                for (int i = 0; i < 4; i++) {
                    int tr = hr + dr[i];
                    int tc = hc + dc[i];
                    if (tr < 0 || row <= tr || tc < 0 || col <= tc) continue;
                    if (im[tr][tc] == '1') continue;
 
                    if (vis[tr][tc] == -1) {
                        vis[tr][tc] = vis[hr][hc] + 1;
                        Q.push(pos(tr, tc));
                        //if (vis[tr][tc] >= ans) is_over_ans = true;
                    }
                }
                //if (is_over_ans) break;
            } // BFS 
            im[r][c] = '1';
            //if (is_over_ans) continue;
 
            int res = vis[row - 1][col - 1];
            if (res != -1) {
                ans = (res > ans) ? ans : res;
            }
            
        }
    }
    if (ans == INF) puts("-1");
    else printf("%d\n", ans);
 
    return 0;
}

#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
 
const int dr[] = { 0,0,-1,1 };
const int dc[] = { -1,1,0,0 };
const int m = 1111;
const int INF = 1 << 22;
 
char im[m][m];
int vis[2][m][m];
int row, col;
 
struct pos {
    int r, c;
    int breaker;
    pos(int ir, int ic, int ib) : r(ir), c(ic), breaker(ib) {}
};
int main() {
    scanf("%d%d", &row, &col);
    for (int r = 0; r < row; r++) {
        scanf("%s", im[r]);
    } // input
 
    int ans = INF;
 
    //for (int r = 0; r < row; r++) {
    //    for (int c = 0; c < col; c++) {
    memset(vis, -1, sizeof(vis));
    queue<pos> Q = queue<pos>();
    Q.push(pos(0, 0, 1));
    vis[1][0][0] = 1;
    while (!Q.empty()) {
        pos here = Q.front();
        Q.pop();
        int hr = here.r;
        int hc = here.c;
        int hb = here.breaker;
 
        for (int i = 0; i < 4; i++) {
            int tr = hr + dr[i];
            int tc = hc + dc[i];
            if (tr < 0 || row <= tr || tc < 0 || col <= tc) continue;
 
            if (im[tr][tc] == '1') {
                if (hb == 0) continue;
                if (vis[hb - 1][tr][tc] != -1) continue;
                vis[hb - 1][tr][tc] = vis[hb][hr][hc] + 1;
                Q.push(pos(tr, tc, hb - 1));
            }
            else if (im[tr][tc] == '0') {
                if (vis[hb][tr][tc] != -1) continue;
                vis[hb][tr][tc] = vis[hb][hr][hc] + 1;
                Q.push(pos(tr, tc, hb));
            }
        }
    }
    //    }
    //}
 
    for (int i = 0; i < 2; i++) {
        if (vis[i][row - 1][col - 1] == -1) continue;
        int res = vis[i][row - 1][col - 1];
        ans = (res > ans) ? ans : res;
    }
    if (ans == INF) puts("-1");
    else printf("%d\n", ans);
 
    return 0;
}