[BOJ 백준] 16973번 직사각형 탈출

문제

BOJ 16973 : https://www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

접근

 문제 접근법을 빠르게 생각해 내서 수월할 거라 예상했지만 의외로 많이 틀렸던 문제이다. 

 문제 접근법은 간단하다. BFS를 통해 시작 좌표 (Sr, Sc)부터 도착 좌표 (Fr, Fc)에 도착할 때까지 while문을 도는 것이다. 여기까지 생각해 내기는 쉽지만 다들 작은 실수로 시간 초과, 메모리 초과, 런타임 에러 등을 겪는다. 왜 이런 오류가 생기는지 하나하나 짚어보겠다.

 

1. 시간 초과

  나의 경우 BFS 과정에서 매번 H x W 크기만큼의 직사각형에 벽이 있는지 매번 검사해 주었다. 그러니 당연히 시간초과가 날 수밖에 없었다. 이 경우 BFS를 돌기 전에 미리 갈 수 없는 좌표를 visit에 체크해주고 시작하면 해결된다.

 

2. 런타임 에러

 우리는 이 문제를 풀 때 직사각형의 좌측 상단의 좌표를 기준으로 코딩을 하고 있기 때문에 직사각형의 크기만큼 공간을 확보해야 한다는 사실을 쉽게 간과한다. 예를 들면 BFS에서 다음 좌표를 push하기 위해 newx, newy가 유효한 좌표인지 확인하는 if문을 썼다고 하자. 평소대로 여느 BFS문제를 풀듯이 코드를 짰다면 if (newx < 1 || newy < 1 || newx > n || newy > m) continue; 이런 식으로 짰을지도 모른다. 하지만 이 문제는 앞서 말했듯이 직사각형의 좌측 상단의 좌표이다. 즉 직사각형의 크기만큼 오른쪽 아래로 공간을 더 요구한다는 뜻이다. 이렇게 되면 기존 배열을 벗어나는 상황이 올 수도 있다. 그러니 반드시 직사각형임을 감안하여 코드를 짜야 한다. (아래 코드 참고) 이 이유가 아니더라도 런타임 에러는 주로 배열에 할당된 크기를 넘어서 접근했을 때 자주 발생한다.

 

3. 메모리 초과

 사실 이 문제를 BFS로 풀었다면 메모리 초과를 만날 일은 잘 없다. 이건 그냥 내가 바보 같은 실수를 한 건데, 도착 좌표 (Fr, Fc)에 도착하면 그대로 BFS를 끝마치면 된다. 즉 break; 를 해주면 된다는 것이다. 근데 continue; 를 해주는 바람에(...) queue가 계속 돌았다. 동시에 한 번 방문한 좌표는 다시 방문하지 않아도 되는데 그 부분 처리를 제대로 못 해줬다. 당연히 메모리 초과가 난다. 메모리 초과는 보통 재귀 함수를 쓸 때 많이 발생한다. 만일 메모리 초과가 났다면 BFS를 구현하는 부분에 있어서 실수 한 점이 없나 다시 한번 확인해보자.

 

코드

#include <iostream>
#include <queue>

using namespace std;

int n, m, h, w, sr, sc, fr, fc;
bool map[1010][1010];
int visit[1010][1010], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> map[i][j];
            visit[i][j] = -1;
        }
    }
    cin >> h >> w >> sr >> sc >> fr >> fc;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (map[i][j] == 1) {
                for (int k = i; k > i - h; k--) {
                    for (int l = j; l > j - w; l--) {
                        if (l < 1 || k < 1)
                            continue;
                        visit[k][l] = -2;
                    }
                }
            }
        }
    }
    if (visit[fr][fc] == -2) {
        cout << -1;
        return 0;
    }

    queue<pair<int, int>> q;
    q.push({sr, sc});
    visit[sr][sc] = 0;
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        if (p.first == fr && p.second == fc)
            break;

        for (int i = 0; i < 4; i++) {
            int newx = p.first + dx[i];
            int newy = p.second + dy[i];
            if (newx < 1 || newy < 1 || newx + h - 1 > n || newy + w - 1 > m || visit[newx][newy] != -1)
                continue;
            q.push({newx, newy});
            visit[newx][newy] = visit[p.first][p.second] + 1;
        }
    }
    cout << visit[fr][fc];
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study