[백준 2194번] 유닛 이동시키기 (C++)

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

2194번: 유닛 이동시키기

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

int N, M, A, B, K;
int s1, s2, e1, e2;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool arr[501][501], visited[501][501];
int result = -1; //이동불가일 경우 -1

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

bool check(int y, int x) //사각형 크기만큼 움직이며 장애물 체크
{
    for(int i=0; i<A; i++)
    {
        for(int j=0; j<B; j++)
        {
            if(arr[i+y][j+x]) return 0;
        }
    }
    return 1;
}

void bfs(int y, int x)
{
    queue<info>q;
    visited[y][x]=1;
    q.push({y, x, 0});

    while(!q.empty())
    {
        auto[yy, xx, count] = q.front();
        q.pop();

        if(yy == e2 && xx == e1) 
        {
            result=count; //목적지 도착
            break;
        }

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

            if(ny<1 || nx <1 || ny+A-1 >N || nx+B-1 >M) continue;
            if(visited[ny][nx] || !check(ny, nx)) continue;
            visited[ny][nx]=1;
            q.push({ny, nx, count+1});
        }
    }
    cout << result;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
   
    cin >> N >> M >> A >> B >> K;
    while(K--)
    {
        int y, x; 
        cin >> y >> x;
        arr[y][x]=1; //장애물 표시
    }
    cin >> s2 >> s1;
    cin >> e2 >> e1;
    bfs(s2, s1);
    return 0;
}

 

보통 기본적인 bfs는 움직이는 물체가 1x1의 형태이지만 이를 변형하여 AxB의 형태를 가진 물체를 움직이며 확인하는 문제이다.

그리고 장애물이 존재하기에 장애물을 따로 표시해줄 배열을 선언한다. (arr)

 

이후 입력받은 시작점은 s2, s1을 기준으로 bfs탐색을 시작한다.

기본적은 구조는 흔히 아는 bfs 알고리즘이다.

다만 여기서 bfs에 값을 3개를 넘겨주므로, 구조체를 사용하여 3개의 값을 받도록 하였다.

 

다음 값이 범위을 넘어서지 않도록 체크해주고, 이때 주의해야 할 것은 사각형의 크기까지 고려한 ny+A, nx+B까지 확인해줘야 한다.

이후 방문여부와 장애물이 범위내에 있는지도 추가적으로 확인해준다.

다음 값을 기준으로 사각형의 크기은 A, B만큼 움직여서 해당 위치에 장애물이 존재한다면 false를 반환하도록해준다.

 

무사히 위 조건들을 넘겼다면 해당 값에 대해 방문처리 및 카운팅을 + 1하여 큐에 넣어준다.

이를 반복하여 무사히 목적지에 도착하면 카운팅했던 값을 결과값에 담아주고 이를 출력해준다.

그리고 이동이 불가한 경우 -1을 출력하도록 하였기 때문에 결과값의 기본값을 -1로 초기화해준다.