백준 g3 14442 벽 부수고 이동하기 2 c++

https://www.acmicpc.net/problem/14442

런타임 에러는 함수가 int를 반환해야 하는데 아무것도 반환하지 않아서 생긴 에러

 

 

풀이

bfs를 돌릴 때, 자신이 부순 벽 개수랑 같이 이동한다.

이때 vis 배열을 2차원으로 두면 벽 부수고 이동한 거리 3 vs 벽 안 부수고 이동한 거리 5 둘 중 뭘 남길건지 애매해지기 때문에 dp처럼 모두 기록할 수 있도록 [n, m, 벽 부순 횟수] 3차원 배열로 둬야 한다.

 

BFS

만약 다음 위치가 벽이 아니면, 그대로 BFS

다음 위치가 벽이면, vis[nx, ny, k+1]이 방문 되었는지 k+1가 K를 넘지 않는지 체크 후 기록

 

/*boj g3 14442 벽 부수고 이동하기 2*/
#include <iostream>
#include <queue>
#include <tuple>
#define MAXN 1005
#define MAXK 12
using namespace std;

int N, M, K;
int vis[MAXN][MAXN][MAXK];
int board[MAXN][MAXN];

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

void print() {
    cout << "\n======================\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << vis[i][j][1] << " ";
        }
        cout << "\n";
    }
}

void input() {
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char a;
            a = cin.get();
            while (a != '0' && a != '1')
                a = cin.get();

            board[i][j] = a - '0';
        }
    }
}

void bfs() {
    queue<tuple<int, int, int>> Q;

    Q.push(make_tuple(0, 0, 0));
    vis[0][0][0] = 1;

    while (!Q.empty()) {
        auto [x, y, k] = Q.front();
        Q.pop();

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

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (board[nx][ny] == 0) { // 다음 이동할 위치가 벽이 아닐 때
                if (vis[nx][ny][k] > 0) continue;

                vis[nx][ny][k] = vis[x][y][k] + 1;
                Q.push({nx, ny, k});
            } else if (board[nx][ny] == 1) { // 다음 이동할 위치가 벽일 때
                if (k + 1 > K) continue;
                if (vis[nx][ny][k + 1] > 0) continue;

                vis[nx][ny][k + 1] = vis[x][y][k] + 1;
                Q.push({nx, ny, k + 1});
            }
        }
        // print();
    }
}

void output() {
    int answer = 999999999;

    for (int k = 0; k < MAXK; k++) {
        if (vis[N - 1][M - 1][k] != 0)
            answer = min(answer, vis[N - 1][M - 1][k]);
    }

    if (answer == 999999999)
        answer = -1;

    cout << answer << "\n";
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    bfs();
    // print();
    output();
}

 

새로 알게 된 것

1. cin.get()은 char만 가능

cin : 공백, 개행 이전의 값들을 가져옴

cin.get() : 공백, 개행 포함 한 글자씩 문자(char)로 가져옴

 

2. tuple 편하게 쓰기

Q.push(make_tuple(0, 0, 0)) -> Q.push({0,0,0})

int x = get<0>(cur);
int y = get<1>(cur);
int z = get<2>(cur);

대신

auto [x, y, z] = cur;

c++17 이상에서 가능