[백준] 2206 벽 부수고 이동하기 (C++)

2206번: 벽 부수고 이동하기

 이 문제는 지난 여름 신촌 연합 알고리즘 캠프 DFS,BFS 수업에서 다룬 문제이다. 강사님께서 문제를 푸는 아이디어만 던져주시고 넘어간 문제이다. 수업이 끝나고 문제를 풀어보았을 때에는 구현이 쉽지 않아서 풀지 못했다. 최근 캠프 때 풀지 못했던 문제들을 풀고 있는데, 이 문제도 드디어 해결하였다!!

 

---

풀이

 입력을 받고 bfs를 통해서 1,1에서부터의 최단거리를 구하는 방식으로 문제를 해결하였다.

 

 

이 문제의 특이한 점은 벽을 1번 부신다는 것이다. 따라서 최소거리를 저장할 배열을 dis[1001][1001]이 아닌 dis[1001][1001][2]로 선언하여 문제를 해결하였다. dis배열은 -1로 초기화하고 문제를 풀기 시작하였다. 즉, dis배열의 값이 -1이라면, 아직 그 곳을 방문하지 않았다는 뜻이다.

 

 

dis[i][j][1]은 벽을 뚫지 않았을 때 (1,1)~(i,j)의 최단거리, dis[i][j][0]은 벽을 한 번 뚫었을 때 (1,1)~(i,j)의 최단거리이다. 

 

 

bfs에 이용되는 queue는 다음과 같이 선언하였다. queue에는 {{행,열},남은 벽뚫기 횟수}가 들어간다. 

queue<pair<pair<ll, ll>, ll>> q;

 

 

 

BFS 과정

(1,1)을 시작으로 bfs를 시작한다. nx,ny는 각각 새로 이동할 칸의 행,열이다.

 

(1) 만약 새로 이동할 칸이 벽이고, 아직 찬스를 사용하지 않은 상태(MAP[nx][ny] == 1 && chance)라면?

dis 배열에 찬스를 사용한 최단거리를 적고(dis[nx][ny][0]=dis[x][y]+1), queue에 {{nx,ny},0}을 넣어준다. 

 

(2) 만약 새로 이동할 칸이 벽이 아니고, 아직 방문하지 않은 곳(MAP[nx][ny] == 0 && dis[nx][ny][chance] == -1)이라면?

dis 배열에 최단거리를 적는다.

dis[nx][ny][chance] = dis[x][y][chance] + 1;

 

답 출력 과정

이렇게 BFS가 끝나면, dis[n][m][0]과 dis[n][m][1]중에서 답을 선택해야 한다. 이 때, 시작한 점도 거리에 포함되어야 하므로 답에 +1을 더하여 출력해야 한다.

 

(1) 둘 다 초기값인 -1인 경우

도달할 수 없다는 의미이므로, -1을 출력하자.

 

(2) dis[n][m][0]은 초기값인 -1이고, dis[n][m][1]이 양수인 경우

벽이 없는 경우이다. 그러므로 dis[n][m][0]+1을 출력하자.

 

(3) dis[n][m][0]은 양수이고, dis[n][m][1]이 초기값인 -1인 경우

dis[n][m][1]이 초기값 -1인 것은 벽을 뚫지 않으면 (n,m)에 도달할 수 없다는 뜻이다. 그러므로 dis[n][m][0]+1을 출력하자.

 

(4) 둘 다 양수인 경우

둘 중 최솟값에 1을 더하여 출력해주자.

 

---

코드

#include <iostream>
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

ll n, m;
ll MAP[1001][1001];
ll dis[1001][1001][2]; //dis[i][j][1]이 벽 안뚫고 거리, dis[i][j][0]은 벽 한 번 뚫은 거리
ll dx[4] = { 0,1,0,-1 };
ll dy[4] = { 1,0,-1,0 }; 
string s;

bool inside(ll a, ll b) {
    if (a >= 1 && a <= n && b >= 1 && b <= m) return true;
    else return false;
}

void bfs() {
    queue<pair<pair<ll, ll>, ll>> q;
    q.push({ {1,1},1 }); //{{x,y},남은 찬스 횟수}
    dis[1][1][1] = 0;
    dis[1][1][0] = 0;
    while (!q.empty()) {
        ll x = q.front().first.first;
        ll y = q.front().first.second;
        ll chance = q.front().second;
        q.pop();
        for (ll i = 0; i < 4; i++) {
            ll nx = x + dx[i];
            ll ny = y + dy[i];
            if (inside(nx, ny)) { //이동할 칸이 격자 안에 있는지 확인
                if (MAP[nx][ny] == 1 && chance) {//벽, 찬스사용
                    dis[nx][ny][0] = dis[x][y][1] + 1;
                    q.push({ {nx,ny},0 });
                }
                if (MAP[nx][ny] == 0 && dis[nx][ny][chance] == -1) {
                    dis[nx][ny][chance] = dis[x][y][chance] + 1;
                    q.push({ { nx,ny }, chance });
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    memset(dis, -1, sizeof(dis)); //dis배열 -1로 초기화
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        cin >> s;
        for (ll j = 1; j <= m; j++) {
            MAP[i][j] = s[j - 1] - '0';
        }
    }
    bfs();

    //아래 출력 부분은 위 글에 설명이 있습니다.
    ll ans0 = dis[n][m][0], ans1 = dis[n][m][1];
    if (ans0 < 0 && ans1 < 0) cout << -1 << endl;
    else if (ans0 < 0 && ans1 >= 0) cout << ans1 + 1 << endl;
    else if (ans0 >= 0 && ans1 < 0) cout << ans0 + 1 << endl;
    else cout << min(ans0 + 1, ans1 + 1) << endl;    

    return 0;
}