2024.09.20 풀이
import sys
input=sys.stdin.readline
from collections import deque
dx=[+2, +2, +1, +1, -2, -2, -1, -1]
dy=[-1, +1, -2, +2, -1, +1, -2, +2]
def bfs(a,b, x,y):
queue=deque()
queue.append((a,b))
while queue:
a,b=queue.popleft()
if a==x and b==y:
return arr[a][b]
for i in range(8):
nx=dx[i]+a
ny=dy[i]+b
if 0<=nx<k and 0<=ny<k and arr[nx][ny]==0:
arr[nx][ny]=arr[a][b]+1
queue.append((nx, ny))
t=int(input())
for _ in range(t):
k=int(input())
a,b=map(int, input().split())
x,y=map(int, input().split())
arr=[[0]*(k+1) for _ in range(k+1)]
print(bfs(a,b, x,y))
체크포인트 ⭐️
- BFS/DFS 판별포인트 : "최소이동" 이므로 -> 최단거리 -> BFS 로 접근가능해야함
- 개수 카운트 : "최소 이동 횟수" 이므로 -> 변수에 +1 하는 방법을 사용하여 단계별로 이동 횟수를 기록.
- 개수 카운트 기준
- "최단 경로", "최소 이동 횟수" -> 변수에 +1 하는 방식
- "가능한 경우의 수" -> 직접 카운트하는 방식.
- DFS/BFS 기준
- BFS : 최단경로, 최소 이동 횟수 -> 시작점에서부터 모든 경로를 동일한 레벨(깊이)로 탐색하며, 가장 먼저 목적지에 도달하는 경로를 반환
- DFS : 모든 경로, 모든 가능한 경우 -> 한 경로를 끝까지 탐색한 후에 다른 경로를 탐색하는 방식
(DFS는 특정 경로를 깊게 탐색하다가 목표 지점에 도달하면 그 값을 반환하지만, 이때 그 경로가 최단 경로일지에 대한 보장은 없음)
