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

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

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

이 문제.. 분명 맞게 푼 것 같은데 자꾸 시간초과가 나시는 분들이 있을 것이다.

아래 코드를 보자

if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            // 이미 방문한 경우
            if (visited[nx][ny][wall]) continue;
            if (board[nx][ny] == 0) {
                q.push({nx,ny,ans+1,wall});
                visited[nx][ny][wall] = true;
            } else if (board[nx][ny] == 1) { // 벽을 만난 경우
                if (wall < k) { // 부술 수 있다면
                    if(visited[nx][ny][wall+1]) continue; // <- 여기가 키포인트!
                    // 위 코드 한 줄이 없다면 시간 초과
                    q.push({nx,ny,ans+1,wall+1});
                    visited[nx][ny][wall+1] = true;
                }
            }

nx ny wall에 대해서 방문한 적이 있으면 방문을 하지 않는다는 것은 너무나 잘 아실 것이라 생각한다.

(bfs에서는 재방문하면 무조건 최단거리가 아니게 되니까)

그러나 벽을 부술 수 있는 경우일 때 방문 여부를 검사를 해주지 않는 분들이 많이 계시는 것 같다!

벽을 깨려고 하는 곳에 방문했는지 여부를 체크해주지 않으면 중복 탐색이 되므로 시간 초과가 발생하는 것이다..!

#include <bits/stdc++.h>

using namespace std;

int n,m,k;
string s;
int board[1001][1001];
bool visited[1001][1001][11];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};;

struct P{
    int r, c;       // 현재 위치
    int cnt = 1;    // 지금까지 지나온 칸 수
    int wall = 0;   // 지금까지 부순 벽의 수
};

int bfs(){
    // x,y좌표 + 지나온 칸의 수,벽을 부순 횟수
    queue<P> q;
    P tmp;
    tmp.r = 0; tmp.c=0;
    q.push(tmp);
    visited[0][0][0] = true;

    while(!q.empty()){
        int x = q.front().r;
        int y = q.front().c;
        int ans = q.front().cnt;
        int wall = q.front().wall;
        q.pop();

        if(x==n-1 && y == m-1) return ans;

        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][wall]) continue;
            if (board[nx][ny] == 0) {
                q.push({nx,ny,ans+1,wall});
                visited[nx][ny][wall] = true;
            } else if (board[nx][ny] == 1) { // 벽을 만난 경우
                if (wall < k) { // 부술 수 있다면
                    if(visited[nx][ny][wall+1]) continue;
                    q.push({nx,ny,ans+1,wall+1});
                    visited[nx][ny][wall+1] = true;
                }
            }
        }
    }
    return -1;
}

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

    cin >> n >> m >> k;
    for(int i=0;i<n;i++){
        cin >> s;
        for(int j=0; j<m;j++){
            board[i][j] = s[j]-'0';
        }
    }
    cout << bfs();
}