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

벽 부수고 이동하기 성공

클릭시 이동합니다.

어떻게 풀까?

최단 경로를 구하기위해 단순한 BFS로 풀려고하면 약간의 오류가 생깁니다!

바로, 벽을 부술수 있는가? 의 유무 때문이죠!

따라서, 벽을 부술수 있는지의 여부를 따로 저장하기 위해 visit 배열을 2개 사용합시다!

이렇게 관리하면, 평범하게 BFS를 돌려서 만약, (n,m)에 도착하면, 그 때의 이동 횟수를 출력하면 바로 그것이 최소 거리 입니다!

사실, 이 문제는 이전에 포스팅했던 미로탈출 과 아주 유사합니다!

만약, 잘 이해가 안되시면 해당 포스팅을 확인해 주세용!!

코드

#pragma once
#include<iostream>
#include<cstring>
struct INFO {
    int r, c, cnt;
    bool key;
};
using namespace std;
bool map[1002][1002];
bool visit[2][1001][1001];
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int n, m;
 
INFO que[3000000];
 
bool outBound(int r, int c)
{
    return r <= 0 || r > n || c <= 0 || c > m;
}
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
    char in;
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= m; j++) 
        {
            cin >> in;
 
            map[i][j] = in - '0';
        }
    }
        
    int res = -1;
    int f, r;
    f = r = 0;
    INFO info = { 1,1,1, true};
    que[r++] = info;
    
    while (f != r)
    {
        INFO now = que[f++];
        
        if (now.r == n && now.c == m)
        {
            res = now.cnt;
            break;
        }
 
        for (int d = 0; d < 4; d++)
        {
            INFO next;
            next.r = now.r + dr[d];
            next.c = now.c + dc[d];
            next.cnt = now.cnt + 1;
            if (outBound(next.r, next.c)) continue;
 
            if (map[next.r][next.c]) {
                if (now.key) {
                    if (visit[false][next.r][next.c]) continue;
                    visit[false][next.r][next.c] = true;
                    next.key = false;
                    que[r++] = next;
                }
            }
            else {
                next.key = now.key;
                if (visit[next.key][next.r][next.c]) continue;
                visit[next.key][next.r][next.c] = true;
 
                que[r++] = next;
            }
        }
    }
 
    cout << res << '\n';
 
    return 0;
}

시간 복잡도

모든 맵을 한번 씩 방문하는 경우가 있을 수 있기 때문에, 시간 복잡도는 입니다.