728x90
https://www.acmicpc.net/problem/7562
문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
예제 입출력
풀이
from collections import deque
move = [(1,2), (2,1) , (-1,-2), (-2,-1), (1,-2), (2,-1), (-1,2), (-2,1)]
t = int(input())
for i in range(t):
l = int(input())
present_x, present_y = map(int,input().split())
goal_x, goal_y = map(int,input().split())
matrix = [ [0]*l for _ in range(l)]
visited = [ [0]*l for _ in range(l)]
queue = deque()
queue.append([present_x, present_y])
visited[present_x][present_y] = 1
while queue:
x,y = queue.popleft()
if x == goal_x and y == goal_y:
print(matrix[x][y])
break
for dx, dy in move:
kx, ky = x + dx, y + dy
if 0<=kx<l and 0<=ky<l and not visited[kx][ky]:
visited[kx][ky] = 1
matrix[kx][ky] = matrix[x][y]+1
queue.append([kx,ky])
간단한 너비, 깊이 탐색 문제이다.
나이트가 움직일 수 있는 경로의 수를 move 리스트에 저장해놓고서
체스판의 범위에 맞거나 방문을 했는지 안했는지를 확인하면서 순회해주면 된다.
728x90
'알고리즘 > 백준' 카테고리의 다른 글
[BOJ, 백준] 1806 - 부분합 (Python) (0) | 2022.07.10 |
---|---|
[BOJ, 백준] 14225 - 부분수열의 합 (Python, 파이썬) (0) | 2022.07.07 |
[BOJ, 백준] 14502 - 연구소 (Python) (0) | 2022.06.30 |
[BOJ, 백준] 14502 - 연구소 (Python) (0) | 2022.06.22 |
[BOJ, 백준] 2580 - 스도쿠 (Python) (0) | 2022.06.21 |