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

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

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

 

아이디어

가려는 칸이 0이면 진행한 칸 수인 cnt+1하고 queue에 넣고,

1이라면 cnt+1, block+1해서 push 했다.

 

 

틀림

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 1000;
int N,M,K;
char arr[MAX][MAX];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
queue<tuple<int,int,int,int>> q;
bool visited[MAX][MAX];
int ans = 987654321;
int bfs() {
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int x = get<0>(cur);
        int y = get<1>(cur);
        int cnt = get<2>(cur);
        int block = get<3>(cur);
        if (x == N-1 && y == M-1) {
            if (block <= K) {
                ans = cnt;
                break;
            } else {
                ans = min(ans, cnt);
            }
        }
        else if (block == K+1) {
            return -1;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny]) {
                continue;
            }
            visited[nx][ny] = true;
            if (arr[nx][ny] == '0') {
                q.push({nx, ny, cnt+1, block});
            }
            else if (arr[nx][ny] == '1') {
                q.push({nx, ny, cnt+1, block+1});
            }
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
    q.push({0,0,1,0});
    cout << bfs();
    return 0;
}

 

설명(틀린 이유)

 

 

아래 테스트케이스를 보자.

 

0,0에서 1,0으로, 2,0으로 이동한다고 하자. 

당연히 n,m에 도달할 수 없으므로 다른 길인 'ㄹ'자 모양((0,1) , (0,2), (1,2)...) 으로 가게될것이다.

 

그러나 이미 2,0은 체크된 상태라 재방문 할 수 없다.

 

 

5 5 1
00011
11011
00011
01111
00010

 

 

내가 더 진행할 수 있는 경우는 다음과 같다.

1. 다음 칸이 0인경우

2. 다음 칸이 1이고, 여태 부순 벽의 수보다 하나 더 부수어도 K보다 작거나 같은 경우

 

 

 

그리고 기본조건은

- map의 범위 안쪽일것

 

 

 

 

이것으로 끝나지 않는다. 방문체크를 어떤 방식으로 해줄것인가?

 

 

 

해당 칸+그 칸에 도착하기까지 부수었던 벽의 개수를 전부 기록하는 것이다.

 

아까 말한 예시

5 5 1
00011
11011
00011
01111
00010

를 다시 보자.

 

 

 

1,0 그리고 2,0으로 이동했을 때 부순 벽의 개수는 1이지만

'ㄹ'자 모양으로 이동한다면 2,0을 방문했을 때 부순 벽의 개수는 0이다.

 

 

조건이 다르므로 visited[nx][ny][block]을 체크할 때 false가 되어 재방문할 수 있다.

 

 

 

정답

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 1000;
int N,M,K;
char arr[MAX][MAX];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
queue<tuple<int,int,int,int>> q;
int visited[MAX][MAX][10]; // 현재까지 부순 벽의 수
int ans = 987654321;

// BFS이므로 이미 방문한 곳에 뒤늦게 방문했다면 기존보다 절대로 더 빠른 경로가 아니다.
int bfs() {
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int x = get<0>(cur);
        int y = get<1>(cur);
        int cnt = get<2>(cur);
        int block = get<3>(cur);
        if (x == N-1 && y == M-1) {
            return cnt;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M) {
                continue;
            }
            if (visited[nx][ny][block]) {
                continue;
            }
            if (arr[nx][ny] == '0') {
                visited[nx][ny][block] = 1;
                q.push({nx, ny, cnt+1, block});
            }
            else if (arr[nx][ny] == '1' && block + 1 <= K) {
                visited[nx][ny][block + 1] = 1;
                q.push({nx, ny, cnt+1, block+1});
            }
        }
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
    q.push({0,0,1,0});
    cout << bfs();
    return 0;
}

 

 

 

유사 문제

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

1261번: 알고스팟

 

 

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

2206번: 벽 부수고 이동하기

 

 

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

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