백준 7562 나이트의 이동 Python 3

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ7562.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque
def bfs(sx, sy, ex, ey):
    visit = [[0]*I for _ in range(I)]
    q = deque([[sx, sy, 0]])
    visit[sy][sx] = 1
    while q:
        x, y, cnt = q.popleft()
        if x == ex and y == ey:
            print(cnt)
            return
        for ddx, ddy in zip(dx, dy):
            nx, ny = x+ddx, y+ddy
            if 0 <= nx < I and 0 <= ny < I and not visit[ny][nx]:
                visit[ny][nx] = 1
                q.append([nx, ny, cnt+1])
input = sys.stdin.readline
T = int(input())
dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [-1, -2, -2, -1, 1, 2, 2, 1]
for _ in range(T):
    I = int(input())
    sx, sy = map(int, input().split())
    ex, ey = map(int, input().split())
    bfs(sx, sy, ex, ey)

---

풀이 과정

풀이 시간 18분

import sys
from collections import deque

def bfs(sx, sy, ex, ey):
	#체스판의 칸 방문처리
    visit = [[0]*I for _ in range(I)]
    q = deque([[sx, sy, 0]])
    visit[sy][sx] = 1
    
    while q:
        x, y, cnt = q.popleft()
        
        #목적지에 도착한 경우, 이동 횟수 출력하고 함수 종료
        if x == ex and y == ey:
            print(cnt)
            return
            
        #이동할 8가지 방향 탐색
        for ddx, ddy in zip(dx, dy):
            nx, ny = x+ddx, y+ddy
            #이전에 방문하지 않은 칸이라면, 방문하고 큐에 삽입한다
            if 0 <= nx < I and 0 <= ny < I and not visit[ny][nx]:
                visit[ny][nx] = 1
                q.append([nx, ny, cnt+1])
                
input = sys.stdin.readline
T = int(input())

#나이트의 이동
dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [-1, -2, -2, -1, 1, 2, 2, 1]

for _ in range(T):
    I = int(input())
    sx, sy = map(int, input().split())
    ex, ey = map(int, input().split())
    bfs(sx, sy, ex, ey)