Baekjoon 19952번 인성 문제 있어??

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int h, w, o, f, xs, ys, xe, ye;
int x, y, l;
int maze[101][101];
int visited[101][101];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};

bool bfs(){
    queue<tuple<int, int, int>> q;
    q.push(make_tuple(xs, ys, f));
    visited[xs][ys] = 1;
    while(!q.empty()){
        int cx = get<0>(q.front());
        int cy = get<1>(q.front());
        int force = get<2>(q.front());
        q.pop();
        if(cx == xe && cy == ye) return true;
        for(int i = 0; i < 4; i++){
            int nx = cx+dx[i];
            int ny = cy+dy[i];
            if(1 <= nx && nx <= h && 1 <= ny && ny <= w){
                if(force < maze[nx][ny]-maze[cx][cy] || force == 0) continue;
                if(!visited[nx][ny]){
                    q.push(make_tuple(nx, ny, force-1));
                    visited[nx][ny] = 1;
                }
            }
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> h >> w >> o >> f >> xs >> ys >> xe >> ye;
        memset(maze, 0, sizeof(maze));
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < o; i++){
            cin >> x >> y >> l;
            maze[x][y] = l;
        }
        if(bfs())
            cout << "잘했어!!\n";
        else
            cout << "인성 문제있어??\n";
    }
    return 0;
}

처음 문제를 읽고 경로가 모두 고유하다고 생각해서 백트래킹으로 접근했었다. 틀리고 나서 문제를 다시 읽어보니 경로가 겹칠 수 있지만 같은 위치에 먼저 도착할수록 남은 힘이 크기 때문에 다른 경로는 생각해 볼 필요가 없었던 것이었다. 따라서 bfs 로 풀이가 가능하다.

단순 bfs 문제였지만 어렵게 ac 를 받았다. 그 이유는 전역변수로 선언한 queue 때문이였다. 테스트 케이스가 여러개 있는 경우 하나의 queue 를 공유해서 사용하게 되므로 이전의 남아있는 값이 다음 결과에 영향을 주게 된다. 앞으로 bfs 문제를 풀이할 때 신경써야 할 부분이 하나 더 생겼다. 되도록이면 queue 는 bfs 함수 안에 작성하자.

시간초과가 나는 백트래킹 풀이로부터는 허용 스택의 사이즈를 알아낼 수 있었다. 깊이가 최대 1만이기 때문에 시간초과가 나야 했지만 메모리 초과가 먼저 발생했다. 정답을 출력하기 전에 재귀로 누적된 지역변수의 메모리 크기가 스택의 허용 메모리 크기를 초과했기 때문이였다. 아래 질문의 답변에서는 백준 서버의 스택 사이즈가 64mb 정도까지 허용된다고 한다.

참고

이 문제를 dfs(재귀)로 풀면 최악의 경우 depth가 100만 아닌가요??