백준 16933번 벽 부수고 이동하기 3 - tuple (C++)

문제 링크 : https://www.acmicpc.net/problem/16933

16933번: 벽 부수고 이동하기 3

 

이 문제는 백준 14442번 벽 부수고 이동하기 2의 상위호환 버젼이다.

백준 14442번 벽 부수고 이동하기 2 (C++)

기본적으로 14442번과 공통된 부분은 해설을 생략하고, 핵심적으로 낮과 밤을 구분하는 방법만 다룰 예정이니 이해가 안되는 부분은 위의 링크를 참고하여 확인하면 된다.

 

문제 풀이는 다음과 같다.

 

1. 이 문제를 풀기위해 큐에 저장해야하는 값들은 다음과 같다.

• y좌표
• x좌표
• 벽을 부순 횟수
• 누적 이동 횟수
• 낮과 밤 여부

최소한 5개의 인자를 큐에 저장해야 하는데, 이를 위해 3개의 쌍으로 나누어 저장해야 한다.

pair로 저장 가능한 최대 쌍은 2쌍까지이기 때문에, 3개의 쌍을 저장하기 위해 tuple + queue를 활용했다.

queue와 tuple을 활용하여 5가지 인자를 저장하는 방법은 아래와 같다.

    queue<tuple<pair<pair<int, int>, pair<int, int>>, int>>q;
    q.push({ {{1,1},{0,1}},0 });
    ch[1][1][0] = true;
    while (!q.empty()) {
        y = get<0>(q.front()).first.first;
        x = get<0>(q.front()).first.second;
        wall = get<0>(q.front()).second.first;
        cnt = get<0>(q.front()).second.second;
        day = get<1>(q.front()); // day = 0 낮, day = 1 밤
        q.pop();
        . . . 

참고로 tuple을 쓰기 위해 #include <tuple>을 활용해야 한다.

 

 

2. 아래는 4방위로 움직여 갈 수 있는 영역을 탐색하는 코드다.

        for (int i = 0; i < 4; i++) {
            ny = y + my[i];
            nx = x + mx[i];
            if (ny >= 1 && ny <= n && nx >= 1 && nx <= m) {
                if (v[ny][nx] == 0 && !ch[ny][nx][wall]) { // 1
                    ch[ny][nx][wall] = true;
                    q.push({ {{ny,nx},{wall,cnt + 1} },abs(day - 1) }); // abs덕에 0,1,0,1만 저장됨
                }
                else if (v[ny][nx] == 1 && wall < k && day == 0 && !ch[ny][nx][wall + 1]) { // 2
                    ch[ny][nx][wall + 1] = true;
                    q.push({ {{ny,nx},{wall + 1,cnt + 1} },abs(day - 1) });
                }
                else if (v[ny][nx] == 1 && wall < k && day == 1 && !ch[ny][nx][wall + 1]) { // 3
                    q.push({ {{y,x},{wall,cnt + 1} },abs(day-1) });
                }
            }
        }

(1) 탐색 영역이 0(=이동할 수 있는 범위)이고, 아직 방문하지 않았다면 방문 표시를 해준 뒤 큐에 삽입해주면 된다.

이때 cnt의 값을 +1 해주고, 낮일 경우 밤으로, 밤일 경우 낮으로 저장해주는 것을 잊지 말자.

(2) 탐색 영역이 1(=벽), 벽을 부순 횟수가 k를 초과하지 않음, 낮, 아직 방문하지 않은 영역일 경우 방문 표시를 해준 뒤 큐에 삽입한다. 이때 wall +1, cnt +1, 낮일 경우 밤, 밤일 경우 낮으로 저장해주는 것을 잊지 말자.

(3) 탐색 영역이 1(=벽), 벽을 부순 횟수가 k를 초과하지 않음, 밤, 아직 방문하지 않은 영역일 경우, cnt의 값을 +1 해주고 낮일 경우 밤, 밤일 경우 낮으로 저장한 뒤 큐에 삽입해준다.

 

이 과정만 잘 이해하면 문제를 푸는데 어려움이 없을 것이다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <tuple>
using namespace std;

int n, m, k, y, x, ny, nx, my[] = { 1,0,-1,0 }, mx[] = { 0,1,0,-1 }, wall, cnt, day;
vector<vector<int>> v;
vector<vector<vector<bool>>> ch;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    char temp;
    cin >> n >> m >> k;
    v.resize(n + 1, vector<int>(m + 1));
    ch.resize(n + 1, vector<vector<bool>>(m + 1, vector<bool>(k + 1)));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> temp;
            v[i][j] = temp - '0';
        }
    }
    queue<tuple<pair<pair<int, int>, pair<int, int>>, int>>q;
    q.push({ {{1,1},{0,1}},0 });
    ch[1][1][0] = true;
    while (!q.empty()) {
        y = get<0>(q.front()).first.first;
        x = get<0>(q.front()).first.second;
        wall = get<0>(q.front()).second.first;
        cnt = get<0>(q.front()).second.second;
        day = get<1>(q.front()); // day = 0 낮, day = 1 밤
        q.pop();
        if (y == n && x == m) {
            cout << cnt << "\n";
            exit(0);
        }
        for (int i = 0; i < 4; i++) {
            ny = y + my[i];
            nx = x + mx[i];
            if (ny >= 1 && ny <= n && nx >= 1 && nx <= m) {
                if (v[ny][nx] == 0 && !ch[ny][nx][wall]) {
                    ch[ny][nx][wall] = true;
                    q.push({ {{ny,nx},{wall,cnt + 1} },abs(day - 1) });
                }
                else if (v[ny][nx] == 1 && wall < k && day == 0 && !ch[ny][nx][wall + 1]) {
                    ch[ny][nx][wall + 1] = true;
                    q.push({ {{ny,nx},{wall + 1,cnt + 1} },abs(day - 1) });
                }
                else if (v[ny][nx] == 1 && wall < k && day == 1 && !ch[ny][nx][wall + 1]) {
                    q.push({ {{y,x},{wall,cnt + 1} },abs(day-1) });
                }
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}

 

벽 부수기는 이제 안녕~ 함께해서 재미있었고 두 번은 귀찮으니까 만나지 말자.