BOJ 16509 - 장군

문제

백준 온라인 저지 - 16509번

풀이 과정

상 이 움직일 수 있는 방법을 고려하여 왕 에게 도달 가능한 최소시간을 구하는 문제입니다.

문제에 제시된 방법으로 상 을 BFS 를 이용해 최소시간을 구할 수 있으며 이때 주의할 점은
상의 이동 경로가 격자를 벗어나거나 다른 물체가 있으면 안된다는 것입니다.

따라서 경로상의 모든 지점을 확인하는 check_path 함수를 구현하고 만약 통과할 경우에만
해당 지점으로 탐색을 이어가는 방법으로 구현했습니다.

코드

import sys
from collections import deque

sang = list(map(int, sys.stdin.readline().split()))
king = list(map(int, sys.stdin.readline().split()))


path_finder = {
    0: [[-1, 0], [-1, -1], [-1, -1]],
    1: [[-1, 0], [-1, 1], [-1, 1]],
    2: [[0, 1], [-1, 1], [-1, 1]],
    3: [[0, 1], [1, 1], [1, 1]],
    4: [[1, 0], [1, 1], [1, 1]],
    5: [[1, 0], [1, -1], [1, -1]],
    6: [[0, -1], [1, -1], [1, -1]],
    7: [[0, -1], [-1, -1], [-1, -1]],
}


def check_path(x, y, i):
    for idx, [dx, dy] in enumerate(path_finder[i]):
        x, y = x + dx, y + dy
        if x < 0 or x > 9 or y < 0 or y > 8:
            return [False, None]
        elif idx != 2 and [x, y] == king:
            return [False, None]

    return [True, [x, y]]


def bfs():
    visit = [[0] * 9 for _ in range(10)]
    q = deque()

    visit[sang[0]][sang[1]] = 1
    q.append([*sang, 0])

    while q:
        x, y, cost = q.popleft()
        if [x, y] == king:
            return cost

        for i in range(8):
            is_reachable, next = check_path(x, y, i)
            if is_reachable:
                nx, ny = next
                if not visit[nx][ny]:
                    visit[nx][ny] = 1
                    q.append([nx, ny, cost + 1])

    return -1


def solution():
    answer = bfs()

    return answer


print(solution())