[백준 16973번] 직사각형 탈출 (C++)

문제링크 : https://www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, H, W, Sr, Sc, Fr, Fc;
int arr[1002][1002];
bool visited[1002][1002];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

struct info
{
    int y, x, cnt;
};

bool func(int y, int x, int idx) //이동가능여부 확인
{
    if(idx == 0) //1, 0 (오른쪽)
    {
        int nx = x+W-1;

        for(int i=y; i<y+H; i++) 
        {
            if(arr[i][nx]) return 1;
        }
    }
    else if(idx == 1) //-1, 0 (왼쪽)
    {
        for(int i=y; i<y+H; i++) 
        {
            if(arr[i][x]) return 1;
        }
    }
    else if(idx == 2) //0, 1 (아래)
    {
        int ny = y+H-1;

        for(int i=x; i<x+W; i++)
        {
            if(arr[ny][i]) return 1;
        }
    }
    else if(idx == 3) //0, -1 (위)
    {
        for(int i=x; i<x+W; i++)
        {
            if(arr[y][i]) return 1;
        }
    }
    return 0;
}

int bfs(int y, int x)
{
    queue<info>q;
    q.push({y, x, 0});
    visited[y][x]=1;
    while(!q.empty())
    {
        auto [yy, xx, cnt] = q.front();
        q.pop();

        if(yy == Fr && xx == Fc) return cnt; //목표 위치 도달

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

            if(ny < 1 || nx < 1 || nx+W-1 > M || ny+H-1 > N) continue; //범위 조건
            if(func(ny, nx, i) || visited[ny][nx]) continue;
            visited[ny][nx]=1;
            q.push({ny, nx, cnt+1});
            
        }
    }
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            cin >> arr[i][j];
        }
    }

    cin >> H >> W >> Sr >> Sc >> Fr >> Fc;
    cout << bfs(Sr, Sc);

    return 0;
}

bfs를 통해서 움직인 각 좌표와 추가적으로 해당 좌표를 기준으로 사각형의 범위가 올바른지 확인해야 한다.

움직이는 방향이 상하좌우 4방향이기에 이에 맞춰서 사각형의 범위를 체크한다.

 

오른쪽이나 왼쪽으로 움직이는 경우에는 움직인 이후 해당 x값을 기준으로 사각형의 y좌표 만큼을 반복문을 돌려서 벽이 있는지 없는지를 확인한다. (세로로 긴 형태의 사각형 탐색)

오른쪽의 경우 값이 늘어나기에 이에 맞춰서 x값을 조정해줘야 한다.

 

위나 아래쪽으로 움직이는 경우에는 움직인 이후 해당 y값을 기준으로 사각형의 x좌표 만큼을 반복문을 돌려서 벽이 있는지 없는지를 확인한다. (가로로 긴 형태의 사각형 탐색)

아래쪽의 경우 값이 늘어나기에 이에 맞춰서 y값을 조정해줘야 한다.

 

이번 문제를 굉장히 많이 틀렸는데..

작은 사각형의 상하좌우를 탐색하는 부분에서 idx == 0이라고 써야하는 것을 idx = 0이라고 썼다..

예제케이스를 통과해서 아무의심이 없었는데 엄청나게 틀리다가 친구에게 검토받고 알게되었다.

어쩐지 런타임 에러로 OutOfBounds가 뜨는게 도저히 이해가 안갔는데.. 알고보니 작은 사각형이 멋대로 돌아다니고 있는 걸 체크를 안한 것이었다.