[Python] 7562번 나이트의 이동

✏️ 문제

 

문제 파악

최소 이동 거리를 구하므로 BFS를 사용해야 한다.

또한 나이트는 8가지 방법으로 움직일 수 있으므로 다음과 같이 방향 배열을 구성했다.

d = [(-2, -1), (2, -1), (-2, 1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)]

 

x, y 좌표를 deque에 넣을 땐 "q = deque([(x, y)])" 라는 걸 알고 있자!

 

알고리즘

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

 

 

코드

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

for _ in range(int(input())):
  l = int(input())
  visited = [[0] * l for __ in range(l)]
  d = [(-2, -1), (2, -1), (-2, 1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)]
  start_x, start_y = map(int, input().split())
  goal_x, goal_y = map(int, input().split())

  def bfs(x, y):
    q = deque([(x, y)])
    visited[x][y] = 1

    while q:
      node_x, node_y = q.popleft()

      for i in range(8):
        dx = node_x + d[i][0]
        dy = node_y + d[i][1]

        if 0 <= dx < l and 0 <= dy < l and visited[dx][dy] == 0:
          visited[dx][dy] = visited[node_x][node_y] + 1
          q.append((dx, dy))
      
      if node_x == goal_x and node_y == goal_y:
        break

  bfs(start_x, start_y)
  print(visited[goal_x][goal_y] - 1)

 

 

 

---

 

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

[알고리즘] DFS와 BFS