[ 백준 / 파이썬 ] 7562. 나이트의 이동

🎉 문제

 

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

 

 

🎉 풀이

✅ bfs 이용

✅ queue에 좌표, 이동횟수를 담아서 목적지에 도달할 때까지 돌렸음

✅ 최소 횟수 출력이기때문에 방문체크 해주면서 돌림

 

 

🎉 코드

from collections import deque

t = int(input()) #tc

for _ in range(t):
  n = int(input()) #체스판 한 변의 길이

  i, j = map(int, input().split()) #지금 위치
  gi, gj = map(int, input().split()) #목적지

  queue = deque()

  queue.append([i, j, 0]) #큐에 지금 위치 추가
  
  #나이트가 이동할 수 있는 8방향
  di = [-2, -1, 1, 2, 2, 1, -1, -2]
  dj = [1, 2, 2, 1, -1, -2, -2, -1]

  #이미 다녀간 곳인지 아닌지 체크
  visited = [[False]*n for _ in range(n)]

  answer = 0
  while queue:
    #좌표, 이동횟수
    a, b, cnt = queue.popleft()

    #목표에 도달하면
    if a == gi and b == gj:
      #이동횟수를 답으로 갱신해주고 while문 break
      answer = cnt
      break

    #8방향 탐색
    for k in range(8):
      ni = a + di[k]
      nj = b + dj[k]

      #탐색할 수 있는 좌표면서
      if 0 <= ni < n and 0 <= nj < n:
        #이전에 방문하지 않았다면
        if not visited[ni][nj]:
          #거기로 갈 거야~~
          visited[ni][nj] = True
          #큐에 좌표 추가, 1회 증가한 이동횟수 추가
          queue.append([ni, nj, cnt+1])
  
  #정답 출력
  print(cnt)