백준: 16948 데스 나이트

문제

16948번: 데스 나이트

 

문제 풀이

N * N 체스판 내에 데스 나이트가 r1, c1에 있을 때, r2, c2에 방문가능 한지를 판단하는 문제이다. 데스 나이트는 문제에 주어진 것과 같이 6가지 방향으로 움직일 수 있다. 따라서 한 정점으로 부터 방문할 수 있는 모든 경우의 수는 시도 횟수 1로 생각하여야 한다. 데스 나이트가 방문할 수 있는 모든 정점을 다 방문하여도, r2, c2에 도달하지 못한 경우는 답을 찾을 수 없는 경우다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y, visited):
    return 0 <= x < n and 0 <= y < n and not visited[x][y]


def bfs(start):
    q = deque([start])
    visited = [[False] * n for _ in range(n)]
    answer = 0
    dirs = ((-2, -1), (-2, 1), (0, -2), (0, 2), (2, -1), (2, 1))

    while q:
        answer += 1

        for _ in range(len(q)):
            cur_x, cur_y = q.popleft()
            for x, y in dirs:
                next_x, next_y = cur_x + x, cur_y + y
                if [next_x, next_y] == end:
                    return answer

                if visitable(next_x, next_y, visited):
                    visited[next_x][next_y] = True
                    q.append([next_x, next_y])
    return -1


if __name__ == '__main__':
    n = int(stdin.readline())
    locations = list(map(int, stdin.readline().split()))
    start, end = locations[:2], locations[2:]
    print(bfs(start))