[Python] 16948번 데스 나이트

✏️ 문제

 

문제 파악

7562번 나이트의 이동 의 업그레이드 버전인 듯? 똑같이 풀면 쉽게 답이 나온다!

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
graph = [[0] * (n) for _ in range(n)]
visited = [[0] * (n) for _ in range(n)] 
d = [(-2, -1), (-2, 1), (0, -2), (0, 2), (2, -1), (2, 1)]
start_x, start_y, end_x, end_y = map(int, input().split())

def bfs(x, y):
  q = deque([(x, y)])
  visited[x][y] = 0
  
  while q:
    x, y = q.popleft() 

    if x == end_x and y == end_y:
      break

    for i in range(6):
      dx = x + d[i][0]
      dy = y + d[i][1]

      if 0 <= dx < n and 0 <= dy < n and visited[dx][dy] == 0:
        visited[dx][dy] = visited[x][y] + 1
        q.append([dx, dy])
        
bfs(start_x, start_y)
print(-1 if visited[end_x][end_y] == 0 else visited[end_x][end_y])

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS