반응형
https://www.acmicpc.net/problem/7562
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
나이트의 이동 성공
한국어
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 | 256 MB | 38533 | 19291 | 14421 | 49.061% |
문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
<문제풀이>
from collections import deque
t = int(input()) # 테스트 케이스
dx = [-2, -2, 2, 2, 1, 1, -1, -1]
dy = [-1, 1, -1, 1, 2, -2, 2, -2] # 8가지 방향 정의
def bfs(): # bfs 함수정의
while queue:
x, y = queue.popleft()
for i in range(8):
nx = dx[i] + x
ny = dy[i] + y
if nx >= l or ny >= l or nx < 0 or ny < 0:
continue
if graph[nx][ny] == 0:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
for _ in range(t): # 테스트 케이스 만큼 반복
queue = deque()
l = int(input())
graph = [[0] * l for i in range(l)] # l*l 리스트 생성
a, b = map(int, input().split()) # 시작 지점
c, d = map(int, input().split()) # 목적지
if (a, b) == (c, d): # 출발지점과 목적지가 같다면 0 출력
print(0)
continue
queue.append((a, b)) # queue에 시작지점 저장
bfs() # bfs 실행
print(graph[c][d]) # 정답출력
반응형
'알고리즘 풀이' 카테고리의 다른 글
[정렬 알고리즘]-jini (0) | 2022.07.07 |
---|---|
[백준 / Python] 24479번: 알고리즘 수업 -깊이 우선 탐색 1 - jini (0) | 2022.07.05 |
[백준 / Python] 7576번: 토마토 - jini (0) | 2022.07.03 |
[백준 / Python] 2178번: 미로 탐색 - jini (0) | 2022.07.03 |
[백준 / Python] 2667번: 단지번호 붙이기 - jini (0) | 2022.07.02 |
댓글