백준 : 2206 *

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

문제 유형 : BFS

1. 최단거리 탐색문제이므로 BFS탐색이 필요한 문제이다.

2. Queue에는 현재 벽을 몇번 뿌수고 경로로 왔는지에 대한 정보가 필요하다.

3. BFS탐색히 방문한 지점은 다시 방문할 필요가 없다. 하지만 이때 이지점을 오는데 벽을 뿌수고왓는가와 안뿌수고 왓는가에 따라서 경로가 달라진다. 따라서 방분배열은 3차원 bool형식으로 지정한다.

 - 설명

   0,0에서 5,5 로가는 경우는 벽을 뿌수고 5,5 로 가는경우와 벽울 뿌수지 않고 5,5로 가는경우로 나뉜다.

   이럴경우 벽을 뿌술경우에는 안뿌술경우보다 거리가 훨씬 짧을거다 하지만 이제 5,5에서 10,10으로가는경우에는 

   벽을 안뿌순경우는 벽을 뿌술수있다. 하지만 벽을 뿌순경우는 벽을 뿌술수 없다. 이런식으로 벽을 부순 유무에따라       거리가 달라진다. 따라서 벽을 뿌순경우와 뿌수진않은경우는 완전다른 경로라고 생각하고 queue에 넣으면된다. 

 

쉽게 생각하자만 벽을 부순시점에서는 이동하는 말이 하나더 생긴다고 생각하고 quque에 넣고 그말들중에 가장빨리 도착하는 말이 제일 빠른경로라고 생각하면 될거같다.

 

 

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
int arr[1001][1001];
bool check[1001][1001][2];
struct Data {
    int y;
    int x;
    int crush;
    int current;
};
 
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
 
 
 
int BFS() {
    int INF = 987654321;
    queue <Data> q;
    q.push({ 1,1,0,1 });
 
    int y;
    int x;
    int crush;
    int current;
    int ny;
    int nx;
    check[0][0][0] = true;
 
    while (!q.empty()) {
        y = q.front().y;
        x = q.front().x;
        crush = q.front().crush;
        current = q.front().current;
        q.pop();
        
        
 
        if (current >= INF) continue;
 
        if (y == N && x == M) {
            return current;
        }
        
        for (int i = 0;i < 4;i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (ny<1 || nx<1 || ny>N || nx>M) continue;
 
            if (arr[ny][nx] == 1) { //벽
                if (crush == 0) {
                    check[ny][nx][1] = true;
                    q.push({ ny,nx,1,current + 1 });
                }
            }
            else if(arr[ny][nx] == 0 && check[ny][nx][crush] == false){
                check[ny][nx][crush] = true;
                q.push({ ny, nx, crush, current + 1 });
            }
 
        }
 
 
    }
 
 
    return -1;
    
}
int main(void) {
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 1;i <= N;i++) {
        for (int j = 1;j <= M;j++) {
            char c;
            cin >> c;
            arr[i][j] = c - '0';
        }
    }
 
    
    cout<<BFS();
 
 
 
}