[백준/Baekjoon] 14442 벽 부수고 이동하기 2 C++ :: BFS

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

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

---

1. Logic

비슷한 문제인 벽 부수고 이동하기 1(boj - 2206) 과 비슷하게 풀어보았다.

 

2206번 문제에서와 마찬가지로 vis배열 설정이 중요하다. 이번 문제에서는 부실 수 있는 블록의 갯수를 유동적으로 입력받기 때문에 BFS에서 처음 시작구간을 queue에 넣을 때 부실수 있는 block의 갯수를 입력받은 k만큼 넣어준 상태로 0이 될때까지 부셔나가면서 문제를 풀었다.

 

https://go2gym365.tistory.com/52

[백준/Baekjoon] 2206 벽 부수고 이동하기 C++ :: BFS

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m, k;

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

vector<string> vec(1001, "");
int vis[1001][1001][11];

int BFS() {
    queue<pair<pair<int, int>, int>> q;

    vis[0][0][k] = 1;

    q.push({{0, 0}, k});

    while(!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int cnt = q.front().second;

        q.pop();

        if(y == n - 1 && x == m - 1) {
            return vis[y][x][cnt];
        }

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

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

            if(vec[ny][nx] == '1' && cnt > 0 && vis[ny][nx][cnt - 1] == 0) {
                vis[ny][nx][cnt - 1] = vis[y][x][cnt] + 1;
                q.push({{ny, nx}, cnt - 1});
            }

            if(vec[ny][nx] == '0' && vis[ny][nx][cnt] == 0) {
                vis[ny][nx][cnt] = vis[y][x][cnt] + 1;
                q.push({{ny, nx}, cnt});
            }
        }
    }

    return -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;

    for(int i = 0; i < n; i++) {
        cin >> vec[i];
    }

    cout << BFS();
}

---

 

 

3. Feedback

비슷한 문제인 2206번을 풀면서 아이디어는 잘 떠올렸지만 벽을 부수는 부분에서 실수를 해서 푸는데 시간이 오래걸렸다.

BFS에서의 최단 경로는 방문했던 배열은 다시 방문을 하지 않아야 최단거리인데 방문하지 않은 곳만 들어가야한다는 조건을 빼먹은 채 틀린부분을 찾으려니 계속 못찾고 문제를 다시 읽고 난 후에 틀린 부분을 찾아 고쳤다.

로직은 맞는 것 같은데 계속 틀리다면 나를 믿고 문제를 다시한번 살펴보자

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90