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

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

2206번: 벽 부수고 이동하기

나름 신박한 문제 !

일단 최소거리를 구하는것이라서 bfs라고 생각했고 등산로 조성과 비슷한 느낌이라서 flag를 통해 벽을 부순 여부를 유지하고 변경해가며 진행을 해줬다. 문제점은 등산로조성은 dfs완탐으로 벽을 부순여부가 다른 길에 영향을 주지 않지만 해당문제의 경우 다른 길에게 영향을 줬다. (예를 들어 벽을 부수고 간길에 대해 벽을 부수지 않고 온길이 그 길로 갈 수 없다)

이것에 대한 해결방안은 방문배열을 3차원으로 선언해서 부수고 온놈들끼리(는 최소를 찾는것이라 서로 영향 X), 혹은 안부수고 온놈들끼리 구분해줘서 서로 영향을 미치지 않게 해주는 것! bfs에서 다른곳에 영향을 주지 않으려면 다중배열로 처리해야하나 부다.

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct Stone{
    int r, c, flag;
};
 
int N, M;
int map[1001][1001], dis[1001][1001][2]; //메인 아이디어!!
int dr[] = { -1,1,0,0 }, dc[] = { 0,0,-1,1 };
queue<Stone> q;
 
void solve() {
    while (!q.empty()) {
        int r = q.front().r, c = q.front().c; 
        int isCrush = q.front().flag; q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr <= 0 || nc <= 0 || nr > N || nc > M || dis[nr][nc][isCrush] != 0) continue;
            if (map[nr][nc] == 0) { //벽없음.
                dis[nr][nc][isCrush] = dis[r][c][isCrush] + 1; //현상황 유지로 q에 넣음.
                q.push({ nr,nc,isCrush });
                if (nr == N && nc == M) { printf("%d\n", dis[nr][nc][isCrush]); return; }
            }
            else if (map[nr][nc] == 1 && isCrush == 0) { //벽 부수기 가능.
                dis[nr][nc][1] = dis[r][c][isCrush] + 1;
                q.push({ nr,nc,1 });//벽을 부숨.
            }
        }
    }
    printf("-1\n"); //실패하는 경우
}
 
int main()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) scanf_s("%1d",&map[i][j]);
    if (N == 1 && M == 1) { printf("1\n"); return 0; } //항상 이런 상황 생각해보기.
    q.push({ 1,1,0 }); dis[1][1][0] = 1;
    solve();
    return 0;
}