벽 부수고 이동하기 2

https://www.acmicpc.net/problem/14442
문제 설명보다는 키포인트를 짚어보겠다.

1. 벽을 부수고 이동한다는 의미

기본: 2차원 배열에서 상하좌우로 이동하며 최단 경로를 찾아간다.
응용: k번 만큼 막혀있는 길인 1을 뚫고 지나갈 수 있다.
=> K번 만큼 길을 뚫고 가는 상태를 visited 배열 상에 나타내야 한다.
어느 분의 말에 따른다면 뚫고 간 상태와 안 뚫고 간 상태를 나타내기 위해서는 차원이 늘어야 한다고 말을 한다.
말이 어렵긴 한데, 자연스럽게 생각해보면 좋을 것 같다.

2. Enum 사용

enum RoadType {
    ROAD,
    BLOCK
};
회사에 취직하기 전엔 코테에서 사용하지 않았던 문법인데 더 알아보기 쉽지 않나 싶어서 써보았다.

3.배열의 크기를 미리 선언 또는 Vector를 이용하여 동적 생성

int board[1001][1001] = { 0, };
bool visited[1001][1001][11] = { false, };
취향 차이라 생각이 들고, 동적 생성하면 오히려 index of range 때문에 더 고민많이 할 것 같아서 미리 생성했다.
두 가지 방법 모두 알고 있는 것이 좋다고 생각한다.

4.struct 사용

struct Info {
    int x;
    int y;
    int k;
    int len;
};
struct는 pair, tuple, class로 사용 가능하다. 2가지 값까지는 pair가 편하다. 다만 3가지 이후로는 tuple은 문법을 또 외워야 한다는 점이 별로다. 그리고 개인적으로 손이 안 익는다. class는 복잡하다. 물론 OOP가 맞지만 여긴 코테니까..그래서 struct 문법을 애용한다.실수를 덜 하게 되는 것다.
또한 큐는 내가 어떻게 이동하고 있는 지에 대한 상태가 저장되는데, 상태의 값을 visited에 옮겨서 struct의 변수의 수를 줄이는 방법도 예전에 사용 많이 했는데, 굳이 그렇게 복잡하게 생각하면 실수를 많이 하게 된다. 상태는 한 곳에 저장해두는 것이 정신 건강 상 좋다.

5.k 값 수정하기

int nk = cur.k + (board[nx][ny] == BLOCK ? 1 : 0);
next_k 값을 구할 때 board[nx][ny] 값을 확인해서 수정해준다. 삼항 연산자로 대체해서 코드의 길이를 줄여보았다.

// 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442
// N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)
// (1, 1)과 (N, M)은 항상 0이라고 가정

// 첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
#include <iostream>
#include <cassert>
#include <vector>
#include <queue>
using namespace std;

enum RoadType {
    ROAD,
    BLOCK
};

struct Info {
    int x;
    int y;
    int k;
    int len;
};

int board[1001][1001] = { 0, };
bool visited[1001][1001][11] = { false, };

int dx[] = { -1, 1,  0, 0 };
int dy[] = { 0, 0, -1, 1 };

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    // 1부터 넣었기 때문에 모든 인덱스는 0부터 시작한다.
    for (int i = 1; i <= n; i++) { 
        string temp;
        cin >> temp;
        for (int j = 1; j <= m; j++) { 
            board[i][j] = temp[j-1] == '0' ? 0 : 1;
        } 
    }

    queue<Info> q;

    q.push({ 1, 1, 0, 0 });
    visited[0][0][0] = true;

    while (!q.empty()) {
        Info cur = q.front(); q.pop();

        if (cur.x == n && cur.y == m) {
            cout << cur.len + 1;
            return 0;
        }

        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;

            int nk = cur.k + (board[nx][ny] == BLOCK ? 1 : 0);
            if (visited[nx][ny][nk] == true) continue;
            if (nk > k) continue;

            q.push({ nx, ny, nk, cur.len + 1 });
            visited[nx][ny][nk] = true;
        }
    }

    cout << -1;
}