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

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

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

문제 풀이는 다음과 같다.

 

1. 먼저 필요한 배열과 변수들을 선언해주고 값을 입력 받는다.

배열의 값은 char 타입으로 주어지므로, 원한다면 char 타입의 배열을 선언해도 되지만 나는 편의상 int형 배열에 값을 저장했다.

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

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)); // 1
    ch.resize(n + 1, vector<vector<bool>>(m + 1, vector<bool>(k + 1))); // 2
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> temp;
            v[i][j] = temp - '0';
        }
    }
    . . .

1번과 2번을 보면 나는 벡터를 resize했다.

배열의 최대 사이즈가 1000*1000*10이므로 int형 배열로 선언해줘도 타임아웃은 안나올테지만, 나는 편의상 벡터로 선언하고 사이즈를 동적할당 해줬다.

 

2. pair형 큐를 만든다. 큐 내부의 위치에 따른 값의 뜻은 다음과 같다.

    queue<pair<pair<int, int>, pair<int, int>>>q;
    q.push({ {1,1},{0,1} }); // {y좌표, x좌표}, {벽을 부순 횟수, 누적 이동거리} 
    ch[1][1][0] = true;

동시에 첫 번째 위치인 ch[1][1][0]은 true로 방문표시를 해준다.

 

3. 아래는 while문의 코드이다. 먼저 간략하게 살펴본뒤 아래 설명을 참고하여 디테일하게 이해해보자.

    while (!q.empty()) {
        y = q.front().first.first; // 1
        x = q.front().first.second;
        wall = q.front().second.first;
        cnt = q.front().second.second;
        q.pop();
        if (y == n && x == m) { // 2
            cout << cnt << "\n";
            exit(0);
        }
        for (int i = 0; i < 4; i++) { // 3
            ny = y + my[i];
            nx = x + mx[i];
            if (ny >= 1 && ny <= n && nx >= 1 && nx <= m) { // 4
                if (v[ny][nx] == 0 && !ch[ny][nx][wall]) { // 5
                    ch[ny][nx][wall] = true;
                    q.push({ {ny,nx},{wall,cnt + 1} });
                }
                else if (v[ny][nx] == 1 && wall < k && !ch[ny][nx][wall + 1]) { // 6
                    ch[ny][nx][wall + 1] = true;
                    q.push({ {ny,nx},{wall + 1,cnt + 1} });
                }
            }
        }
    }

(1) y좌표, x좌표, 벽을 부순 횟수, 누적 이동거리를 각각 변수에 저장해준뒤 큐를 pop한다.

(2) 만약 현재 큐의 front 값이 n,m에 도달했을 경우 정답이므로, cnt를 출력하고 종료한다.

(3) 현재 지점을 기준으로 4방위로 탐색을 진행한다.

(4) 만약 4방위의 위치가 배열의 범위를 벗어나지 않을 경우,

-> (5) 동시에 해당 위치값이 0(=이동할 수 있는 곳)이며 해당 위치를 방문한 적이 없을 경우, 방문 표시를 해준 뒤 큐에 해당 값을 삽입해준다.

-> (6) 반대로 해당 위치가 1(=벽)이며, 아직 벽을 더 부술 수 있을 경우 (wall < k), 동시에 벽을 부숴서 이동한 곳을 방문한 적이 없을 경우, 방문 표시를 해준 뒤 큐에 해당 값을 삽입해준다.

 

4. while문을 빠져나왔을 경우 목표지점에 도달하지 못했다는 뜻이므로, -1을 출력해준다.

    cout << ans << "\n"; // ans = -1
    return 0;

  

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

int n, m, k, y, x, ny, nx, my[] = { 1,0,-1,0 }, mx[] = { 0,1,0,-1 }, wall, cnt, ans = -1;
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<pair<pair<int, int>, pair<int, int>>>q;
    q.push({ {1,1},{0,1} });
    ch[1][1][0] = true;
    while (!q.empty()) {
        y = q.front().first.first;
        x = q.front().first.second;
        wall = q.front().second.first;
        cnt = q.front().second.second;
        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} });
                }
                else if (v[ny][nx] == 1 && wall < k && !ch[ny][nx][wall + 1]) {
                    ch[ny][nx][wall + 1] = true;
                    q.push({ {ny,nx},{wall + 1,cnt + 1} });
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

회사 노트북으로 채점하면 항상 어마무시한 시간이 나온다. 집에서 채점하면 시간이 더 빠르게 나오지 않을까 싶다.