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

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

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

이미 풀어봤던 문제이지만, 더 효율적인 방법이 있기에 한 번 더 해설을 작성한다.

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

이전에는 Tuple을 써서 큐에 원소들을 저장했으나, 생각해보니 구조체(Structure)를 사용하면 더 쉽게 풀 수 있다는 것을 깨달았다.

 

이전 코드랑 모든 과정은 동일하고 다음 두 단계만 다르게 작성했다.

(1) 배열을 저장할 때 문자열을 그대로 저장 (이전에는 int로 변환했다)

(2) Tuple이 아닌 구조체로 원소 저장 후 활용

 

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

int n, m, k, yy, xx, ww, cc, dayornight, my[] = { 0,1,0,-1 }, mx[] = { 1,0,-1,0 }, ny, nx;

struct go {
    int y, x;
    int wall, cnt;
    int day; // 0 = day, 1 = night
};
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> k;
    vector <vector<char>> v(n+1, vector<char>(m+1, 0));
    vector<vector<vector<bool>>> ch(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 >> v[i][j];
    }
    queue<go> q;
    q.push({ 1,1,0,1,0 }); // 구조체니까 중괄호 하나 안에 한번에 모든 원소 입력
    ch[1][1][0] = true;
    while (!q.empty()) {
        yy = q.front().y;
        xx = q.front().x;
        ww = q.front().wall;
        cc = q.front().cnt;
        dayornight = q.front().day;
        q.pop();
        if (yy == n && xx == m) {
            cout << cc << "\n";
            exit(0);
        }
        for (int i = 0; i < 4; i++) {
            ny = yy + my[i];
            nx = xx + mx[i];
            if (ny >= 1 && ny <= n && nx >= 1 && nx <= m) {
                if (v[ny][nx] == '0' && !ch[ny][nx][ww]) { // 통로
                    ch[ny][nx][ww] = true;
                    q.push({ ny,nx,ww,cc + 1,abs(dayornight - 1) });
                }
                else if (v[ny][nx] == '1' && dayornight==0 && ww < k && !ch[ny][nx][ww + 1]) { // 벽 (낮)
                    ch[ny][nx][ww+1] = true;
                    q.push({ ny,nx,ww + 1,cc + 1,abs(dayornight - 1) });
                }
                else if (v[ny][nx] == '1' && dayornight == 1 && ww < k && !ch[ny][nx][ww + 1]) q.push({ yy,xx,ww,cc + 1,abs(dayornight - 1) });// 벽 (밤)
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}

Tuple을 이용했던것 보다 훨씬 효율성이 좋다.