[BOJ 14442 // C++] 벽 부수고 이동하기 2

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14442번 문제인 벽 부수고 이동하기 2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/14442

14442번: 벽 부수고 이동하기 2

이 문제에서는 이동하는 동안 벽을 부술 수 있는 횟수가 정해져있다. 따라서, BFS 탐색을 하되, 각 노드에 벽을 부순 횟수 정보를 추가로 저장하면 문제를 BFS를 이용하여 쉽게 해결할 수 있다.

각 노드에 벽을 부순 횟수를 저장하는 가장 간단한 방법은 좌표를 3개 사용하는 것이다. 좌표를 3개 사용하면 벽을 몇개 부수고 왔는가에 따라 같은 점에 데이터가 따로 저장되게 된다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <tuple>
#include <string>
#include <queue>
using std::cin;
using std::cout;
using std::queue;
using std::string;
using std::tuple;
using std::make_tuple;

queue<tuple<int, int, int>> que;
string map[1001];
int dist[1001][1001][11];

int dt1[4] = { 1,-1,0,0 };
int dt2[4] = { 0,0,1,-1 };
int ans = -1;

int main()
{
    int N, M, K;
    cin >> N >> M >> K;
    for (int i = 1;i <= N;i++) {
        string s; cin >> s;
        map[i] = ' ' + s; // 코딩의 편리성을 위해 앞에 공백을 더해주었다.
    }
    que.push(make_tuple(1,1,0));
    dist[1][1][0] = 1;
    while (!que.empty()) { // BFS
        tuple<int, int, int> current = que.front(); que.pop();
        int t1 = std::get<0>(current), t2 = std::get<1>(current), t3 = std::get<2>(current);
        if (t1 == N and t2 == M) {
            ans = dist[t1][t2][t3];
            break;
        }
        for (int i = 0;i < 4;i++) {
            int r = t1 + dt1[i], c = t2 + dt2[i];
            if (0 < r and r <= N and 0 < c and c <= M) { // r행 c열이 범위 안에 들어있는가
                int b = t3 + ((map[r][c] - '0' == 0) ? 0 : 1); // 이동할 칸이 벽이라면 벽을 부순 횟수 1 추가
                if (b > K) continue; // 벽을 부순 횟수가 K보다 크다면 더 이상 탐색하지 않음
                if (dist[r][c][b]==0) {
                    dist[r][c][b] = dist[t1][t2][t3] + 1;
                    que.push(make_tuple(r, c, b));
                }
            }
        }
    }
    cout << ans;
}