[백준 2194번] 파이썬 - 유닛 이동시키기

백준 2194 - 유닛 이동시키기

시간 제한 2초, 메모리 제한 128MB

# 문제

• 스타크래프트와 같은 게임을 하다 보면 어떤 유닛을 목적지까지 이동시켜야 하는 경우가 종종 발생한다.
• 편의상 맵을 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을 출력한다.

# 접근 방법

• 우선 주어지는 왼쪽 위의 한 점을 바탕으로 bfs를 돌려준다.
• 주어지는 크기만큼의 visited 배열을 만들고 입력받는 장애물의 위치를 기록해준다.
• 다만, 방문 가능한 곳이라면 유닛 전체의 크기를 순회하며 장애물이 있는지 체크해주어야 한다.
• 따라서 이동하는 왼쪽 점의 visited가 방문하지 않았고, 제일 오른쪽 아래의 점이 범위를 벗어나지 않았다면 탐색해준다.
• 장애물이 현재 유닛과 겹치는지를 확인해주는 작업만 한다면 일반적인 bfs와 동일하다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs(ui, uj, ei, ej):  
    q = deque()  
    q.append((ui, uj))  
    visited[ui][uj] = 1  
    while q:  
        si, sj = q.popleft()  
        if (si, sj) == (ei, ej):  
            return visited[ei][ej] - 1  
        for d in range(4):  
            ni, nj = si+di[d], sj+dj[d]  
            # 범위 체크 -> 제일 왼쪽 위 모서리와 제일 오른쪽 아래 모서리  
            if 0<=ni<N and 0<=nj<M and 0<=ni+A-1<N and 0<=nj+B-1<M and visited[ni][nj] == 0:  
                val = check(ni, nj)  
                if val:  
                    visited[ni][nj] = visited[si][sj] + 1  
                    q.append((ni, nj))  

    return -1  

def check(i, j):  
    # 유닛 크기만큼 돌면서 장애물이 있는지 체크해주기  
    for a in range(A):  
        for b in range(B):  
            if visited[i+a][j+b] == -1:  
                return 0  

    return 1  

N, M, A, B, K = map(int, input().split())  
visited = [[0] * M for _ in range(N)]  
di, dj = [1, -1, 0, 0], [0, 0, 1, -1]  
for _ in range(K):  
    a, b = map(int, input().split())  
    visited[a-1][b-1] = -1  

ui, uj = [i-1 for i in map(int, input().split())]  
ei, ej = [i-1 for i in map(int, input().split())]  

print(bfs(ui, uj, ei, ej))