[백준/16973] 직사각형 탈출

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

문제 접근

일반 BFS 문제인데 시간 제한 때문에 좀 빡셌다.

걸린 부분은 벽을 판단하는 로직, 방문 체크 시점 때문이다.

벽을 판단하는 로직의 경우, 처음에는 그 부분을 때서 1이 있는지를 검사했었다. 개선한 로직은 미리 벽 위치를 저장해두고 검사했다.

방문 체크 시점은 큐에서 꺼내서 방문 체크를 했었는데, 다음 좌표로 움직일 수 있는 지를 체크하는 로직에서 해당 좌표를 방문 체크로 변경했다. 이 부분이 제일 핵심이었다.

소스 코드

from collections import deque
from typing import List, Tuple


def is_range(n: int, m: int, r: int, c: int) -> bool:
    return r >= 0 and r <= n and c >= 0 and c <= m


def possible_move(wall: List[Tuple[int]], visit: List[bool], sr: int, sc: int, h: int, w: int) -> bool:
    visit[sr][sc] = True

    for r, c in wall:
        if sr <= r and r < sr + h and sc <= c and c < sc + w:
            return False

    return True


def move_count(wall: List[List[int]], n: int, m: int, h: int, w: int, sr: int, sc: int, fr: int, fc: int) -> int:
    q = deque()
    q.append([sr, sc, 0])

    visit = []
    for _ in range(n):
        visit.append([False] * m)

    d_arr = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    while q:
        r, c, distance = q.popleft()

        if r == fr and c == fc:
            return distance

        for d in d_arr:
            dr, dc = r + d[0], c + d[1]
            if is_range(n - h, m - w, dr, dc) and not visit[dr][dc] and possible_move(wall, visit, dr, dc, h, w):
                q.append([dr, dc, distance + 1])

    return -1


def get_input() -> int:
    n, m = map(int, input().split(" "))
    wall = []

    for i in range(n):
        row = list(map(int, input().split(" ")))

        for j in range(len(row)):
            if row[j] == 1:
                wall.append([i, j])

    h, w, sr, sc, fr, fc = map(int, input().split(" "))
    return move_count(wall, n, m, h, w, sr - 1, sc - 1, fr - 1, fc - 1)


print(get_input())