Python3/백준 알고리즘
2022.02.12 [백준] (python 파이썬) 나이트의 이동
ian's coding
2022. 2. 12. 16:51
728x90
반응형
https://www.acmicpc.net/problem/7562
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
풀이
이 문제는 시작 좌표부터 목표 좌표까지 도달하기 위해 움직여야할 횟수를 출력하는 문제이다.
즉, 이 문제는 a에서 b까지의 최단거리를 구하는 문제이기 때문에 bfs를 이용하여 문제를 해결해야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
from collections import deque
#나이트가 갈 수 있는 거리 저장
dx=[-2,-2,-1,-1,1,1,2,2]
dy=[1,-1,2,-2,2,-2,1,-1]
def bfs(x, y, _x, _y):
#방문해야 할 곳을 저장하는 덱 생성 및 초기화
deq=deque()
deq.append([x, y])
#덱에 데이터가 들어있을때까지 while문 반복
while deq:
#덱에서 먼저 들어간 데이터를 pop하고
#pop한 데이터가 타겟 좌표인 _x, _y와 같으면 arr[x][y]값 리턴
x,y=deq.popleft()
if x==_x and y==_y:
return arr[x][y]
for i in range(len(dx)):
nx=x+dx[i]
ny=y+dy[i]
#나이트가 이동할 좌표의 범위 확인
if 0<=nx<l and 0<=ny<l:
#이동 할 좌표의 값이 0이면 한번도 방문하지 않은 곳
if arr[nx][ny]==0:
deq.append([nx,ny])
arr[nx][ny]=arr[x][y]+1
for _ in range(int(input())):
l=int(input())
# l X l크기의 체스판 생성
arr=[[0]*l for _ in range(l)]
#시작 지점
x,y = map(int, input().split())
#목표 지점
t_x,t_y = map(int, input().split())
ans = bfs(x,y,t_x,t_y)
print(ans)
|
cs |
728x90
반응형