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

백준의 직사각형 탈출(16973) 문제이다.

[ 문제 바로가기 ]

[ 문제 풀이 ]

1) 일반적인 BFS 완전탐색법을 이용하면 쉽게 해결할 수 있는 문제이다. 단지, 일반적으로 하나의 좌표를 움직이는 것이 아닌

   크기가 존재하는 사각형을 한번에 움직여 줘야 한다는 부분만 잘 계산해주면 된다.

   문제에서, 주어진 사각형의 가장 왼쪽 위에 존재하는 칸이, 도착점에 도달하기 위해서 최소 몇번을 움직여야 하는지

   구해야 하는 문제이다.

   움직여 줄 때, 움직여주는 방향에 맞게 사각형의 가로 , 세로길이를 적절하게 계산해주고 판단해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, M, H, W, Sx, Sy, Ex, Ey;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
    cin >> H >> W >> Sx >> Sy >> Ex >> Ey;
    Sx--; Sy--; Ex--; Ey--;
}
 
bool Can_Move(int x, int y, int dir)
{
    if (dir == 0)
    {
        int ny = y + W - 1;
        if (ny >= M) return false;
 
        for (int i = x; i < x + H; i++)
        {
            if (MAP[i][ny] == 1) return false;
        }
    }
    else if (dir == 1)
    {
        for (int i = x; i < x + H; i++)
        {
            if (MAP[i][y] == 1) return false;
        }
    }
    else if (dir == 2)
    {
        int nx = x + H - 1;
        if (nx >= N) return false;
 
        for (int i = y; i < y + W; i++)
        {
            if (MAP[nx][i] == 1) return false;
        }
    }
    else if (dir == 3)
    {
        for (int i = y; i < y + W; i++)
        {
            if (MAP[x][i] == 1) return false;
        }
    }
 
    return true;
}
 
void BFS(int a, int b)
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(a, b), 0));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (x == Ex && y == Ey)
        {
            cout << Cnt << endl;
            return;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (Visit[nx][ny] == false)
                {
                    if (Can_Move(nx, ny, i) == true)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                    }
                }
            }
        }
    }
    cout << -1 << endl;
}
 
void Solution()
{
    BFS(Sx, Sy);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}