[python]7562번 나이트의 이동

 

최단거리 bfs를 활용하는 문제였다.

숨바꼭질과 미로탐색과 다른점이라 하면은 정점의 이동거리만 체스말인 나이트처럼 설정되어있다.

그 외에는 거의 똑같아서 bfs복습문제로 느껴졌다.

 

import sys
from collections import deque
input = sys.stdin.readline
for _ in range(int(input().strip())):  #테스트 케이스 횟수
    size = int(input().strip())
    mtx = [[0 for i in range(size)] for j in range(size)]
    startx,starty = map(int,input().split())
    endx,endy = map(int,input().split())
    stg = deque()
    stg.append((startx,starty,0))
    if startx == endx and starty==endy:    #시작과 끝이 같을 경우 종료
        print(0)
        continue
    while stg:
        cur = stg.popleft()
        for i in [(cur[0]+2,cur[1]+1),(cur[0]+1,cur[1]+2),(cur[0]+2,cur[1]-1),
        			(cur[0]+1,cur[1]-2),(cur[0]-2,cur[1]-1),(cur[0]-2,cur[1]+1),
                    (cur[0]-1,cur[1]+2),(cur[0]-1,cur[1]-2)]:  #나이트 이동거리 설정
            if 0<=i[0]<size and 0<=i[1]<size and not mtx[i[1]][i[0]]:
                if i[0] == endx and i[1]==endy:   #도착한다면 cur에 3번째 인자인 횟수 출력
                    print(cur[2]+1)
                else:
                    stg.append((i[0],i[1],cur[2]+1))   #도착 못했다면 정점 큐에 append하기
                mtx[i[1]][i[0]]=1    #방문했다는 표시, 중복 진입 방지를 위해

 

 

 

 

 

 

 

 

tworiver고수님의 풀이

from collections import deque

T = int(input())
ans = []
for _ in range(T):
  I = int(input())
  board = [[0 for _ in range(I)] for _ in range(I)]
  
  A = list(map(int, input().split()))
  B = list(map(int, input().split()))
  
  q = deque([A])
  board[A[0]][A[1]] = 1
  while q:
    x, y = q.popleft()
    if x==B[0] and y==B[1]:
      break
    pos = [(x+2, y+1), (x+2, y-1), (x-2, y+1), (x-2, y-1),
           (x+1, y+2), (x-1, y+2), (x+1, y-2), (x-1, y-2)]
    for p in pos:
      if 0<=p[0]<I and 0<=p[1]<I:
        if board[p[0]][p[1]]==0:
          board[p[0]][p[1]] = board[x][y]+1     #인자로 횟수를 저장하는것이 아닌, 배열에 값을 저장
          q.append((p[0],p[1]))

  ans.append(board[B[0]][B[1]]-1)

for a in ans:
  print(a)