[Silver I] 나이트의 이동 - 7562(BFS)

[Silver I] 나이트의 이동 - 7562

문제 링크

성능 요약

메모리: 124540 KB, 시간: 316 ms

분류

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

문제 설명

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

import sys
input = sys.stdin.readline
from collections import deque
dx = [-1,-2,-2,-1,1,2,2,1]
dy = [2,1,-1,-2,-2,-1,1,2]
for i in range(int(input())):
  n = int(input()) #한 변의 길이
  now_x, now_y = map(int,input().split()) #현재 좌표
  end_x, end_y = map(int,input().split()) #도달할 좌표
  graph = [[0]*n for i in range(n)]
  q = deque()
  q.append((now_x, now_y))
  while q:
    x, y = q.popleft()
    if x == end_x and y == end_y:
      break
    for j in range(8):
      nx = x + dx[j]
      ny = y + dy[j]
      if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 0:
        graph[nx][ny] = graph[x][y] + 1
        q.append((nx,ny))
  print(graph[end_x][end_y])

최소 이동 횟수를 구하는 문제이므로, BFS를 선택한다.

별다른 BFS 함수 호출 없이 while q를 이용하여 구현했고, 방문 체크를 위해 graph[nx][ny] 좌표의 값이 0일 때만 이전 좌표의 이동횟수에서 1을 더해주면 정답을 찾을 수 있다.