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

2194번 : 유닛 이동시키기

---

문제)

스타크래프트와 같은 게임을 하다 보면 어떤 유닛을 목적지까지 이동시켜야 하는 경우가 종종 발생한다. 편의상 맵을 N×M 크기의 2차원 행렬로 생각하자. 또한 각각의 유닛은 크기를 가질 수 있는데, 이를 A×B 크기의 2차원 행렬로 생각하자. 아래는 5×5 크기의 맵과 2×2 크기의 유닛에 대한 한 예이다. S는 시작점을 나타내며 E는 끝점을 나타낸다.

 

 

유닛은 상하좌우의 네 방향으로만 움직일 수 있다. 단, 유닛의 일부분이 장애물이 설치된 부분(위의 예에서 색이 칠해진 부분)을 지날 경우, 위의 예에서는 시작 위치에서 위로 이동하는 경우는 허용되지 않는다. 위의 예는 유닛을 오른쪽으로 세 칸, 위쪽으로 세 칸 움직이면 목적지에 도달할 수 있고, 이 경우가 가장 적은 이동 회수를 거치는 경우이다. 이동하는 도중에 유닛이 맵 밖으로 나가는 경우는 허용되지 않는다.

맵의 정보와 유닛의 정보가 주어졌을 때, 유닛을 목적지까지 움직이기 위해 필요한 최소의 이동 회수를 구하는 프로그램을 작성하시오.

 

 

입력 :

첫째 줄에 다섯 개의 정수 N, M(1 ≤ N, M ≤ 500), A, B(1 ≤ A, B ≤ 10), K(0 ≤ K ≤ 100,000)가 주어진다. 다음 K개의 줄에는 장애물이 설치된 위치(행 번호, 열 번호)가 주어진다. 그 다음 줄에는 시작점의 위치와 도착점의 위치가 주어진다. 시작점의 위치와 도착점의 위치는 제일 왼쪽 제일 위의 한 점만 주어진다. 시작점의 위치와 도착점의 위치는 같지 않다.

유닛의 시작점에는 장애물이 존재하지 않으며, 시작점과 도착점이 행렬의 범위를 벗어나는 경우는 없다.

 

 

 

출력 :

첫째 줄에 답을 출력한다. 이동이 불가능한 경우에는 -1을 출력한다.

 

 

 

 

 

풀이)

 

// 2194. 유닛 이동시키기
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n, m, a, b, k;
vector<vector<int>> vec;
vector<vector<int>> visited;
 
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
 
int bfs(int s1, int s2, int e1, int e2)
{
    // 유닛의 좌상단, 즉 한 점만을 가지고 움직인다.
    queue<pair<int, int>> q;
    visited[s1 - 1][s2 - 1] = 1;
    q.push(make_pair(s1 - 1, s2 - 1));
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        // 목적지에 도착했다면 이동 거리를 리턴해준다.
        if (x == e1 - 1 && y == e2 - 1)
        {
            return visited[x][y] - 1;
        }
 
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            // 지도 이탈 확인
            if (0 > nx || nx >= n) continue;
            if (0 > ny || ny >= m) continue;
            
            // 방문했던 곳인지 확인
            if (visited[nx][ny]) continue;
 
            // 장애물이 있는 곳인지 확인
            if (vec[nx][ny]) continue;
 
            // 2중 for문을 통해 유닛이 위치할 수 있는지 확인한다.
            bool flag = 0;
            for (int j = nx; j < nx + a; j++)
            {
                for (int k = ny; k < ny + b; k++)
                {
                    // 유닛은 지도 내에 존재해야 하고,
                    // 장애물과 겹쳐있을 수 없으므로.
                    if (0 > j || j >= n
                        || 0 > k || k >= m
                        || vec[j][k])
                    {
                        flag = 1;
                        break;
                    }
                }
                
                if (flag) break;
            }
 
            if (flag) continue;
 
            visited[nx][ny] = visited[x][y] + 1;
            q.push(make_pair(nx, ny));
        }
    }
 
    // 목적지에 도달하지 못하고 queue가 비었다면
    // 갈 수 없다.
    return -1;
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> a >> b >> k;
    vec.resize(n, vector<int>(m, 0));
    visited.resize(n, vector<int>(m, 0));
 
    int t1, t2, t3, t4;
    for (int i = 0; i < k; i++)
    {
        cin >> t1 >> t2;
        t1--; t2--;
        // 장애물 표시
        vec[t1][t2] = 3;
    }
 
    cin >> t1 >> t2 >> t3 >> t4;
 
    cout << bfs(t1, t2, t3, t4);
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/2194 

2194번: 유닛 이동시키기