나이트의 이동 풀이

문제 링크: https://www.acmicpc.net/problem/7562

백준 알고리즘 기초 2/2 600에서 9번째 - 7562번 나이트의 이동을 풀어보았다.

 

풀이: bfs를 쓰는 문제이다.

 

C++

 

Python

from collections import deque

def bfs(a,b,c,d):
	dx=[-1,1,2,2,1,-1,-2,-2]
	dy=[2,2,1,-1,-2,-2,-1,1]
	queue=deque()
	queue.append((a,b))
	while queue:
		x,y=queue.popleft()
		if x==c and y==d:
			return graph[x][y]-1
		for i in range(8):
			nx=x+dx[i]
			ny=y+dy[i]
			if 0<=nx<l and 0<=ny<l and graph[nx][ny]==0:
				graph[nx][ny]=graph[x][y]+1
				queue.append((nx,ny))

t=int(input())
for _ in range(t):
	l=int(input())
	cx,cy=map(int,input().split())
	ox,oy=map(int,input().split())
	graph=[[0]*l for i in range(l)]
	graph[cx][cy]=1
	print(bfs(cx,cy,ox,oy))

Java