[Silver I] 데스 나이트 - 16948

문제 링크

성능 요약

메모리: 32452 KB, 시간: 108 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r₁, c₁), (r₂, c₂)가 주어진다. 데스 나이트가 (r₁, c₁)에서 (r₂, c₂)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r₁, c₁, r₂, c₂가 주어진다.

출력

첫째 줄에 데스 나이트가 (r₁, c₁)에서 (r₂, c₂)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

# 체크판의 크기 n
from collections import deque

dx, dy = [-2, -2, 0, 0, 2, 2], [-1, 1, -2, 2, -1, 1]

n = int(input())
# 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동
r1, c1, r2, c2 = map(int, input().split())

graph = [[0] * n for _ in range(n)]
def bfs():
      visitied = [[0] * n for _ in range(n)]
      visitied[r1][c1] = 1
      q = deque()
      q.append((r1, c1))

      while q:
            x, y = q.popleft()

            for i in range(6):
                  nx, ny = x + dx[i], y + dy[i]

                  if 0 <= nx < n and 0 <= ny < n and not visitied[nx][ny]:
                        visitied[nx][ny] = visitied[x][y] + 1
                        q.append((nx, ny))
                        if nx == r2 and ny == c2:
                              return visitied[nx][ny] - 1
      return -1



print(bfs())