18404번: 현명한 나이트
첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. (
www.acmicpc.net
문제
NxN 크기 체스판의 특정한 위치에 하나의 나이트가 존재한다. 이때 M개의 상대편 말들의 위치 값이 주어졌을 때, 각 상대편 말을 잡기 위한 나이트의 최소 이동 수를 계산하는 프로그램을 작성하시오.
나이트는 일반적인 체스(Chess)에서와 동일하게 이동할 수 있다. 현재 나이트의 위치를 (X,Y)라고 할 때, 나이트는 다음의 8가지의 위치 중에서 하나의 위치로 이동한다.
(X-2,Y-1), (X-2,Y+1), (X-1,Y-2), (X-1,Y+2), (X+1,Y-2), (X+1,Y+2), (X+2,Y-1), (X+2,Y+1)
N=5일 때, 나이트가 (3,3)의 위치에 존재한다면 이동 가능한 위치는 다음과 같다. 나이트가 존재하는 위치는 K, 이동 가능한 위치는 노란색으로 표현하였다.
예를 들어 N=5, M=3이고, 나이트가 (2,4)의 위치에 존재한다고 가정하자. 또한 상대편 말의 위치가 차례대로 (3,2), (3,5), (4,5)라고 하자. 이때 각 상대편 말을 잡기 위한 최소 이동 수를 계산해보자. 아래 그림에서는 상대편 말의 위치를 E로 표현하였다. 단, 본 문제에서 위치 값을 나타낼 때는 (행,열)의 형태로 표현한다.
각 상대편 말을 잡기 위한 최소 이동 수는 차례대로 1, 2, 1이 된다.
입력
첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ X, Y ≤ N) 셋째 줄부터 M개의 줄에 걸쳐 각 상대편 말의 위치 (A, B)를 의미하는 A와 B가 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ A, B ≤ N)
단, 입력으로 주어지는 모든 말들의 위치는 중복되지 않으며, 나이트가 도달할 수 있는 위치로만 주어진다.
출력
첫째 줄에 각 상대편 말을 잡기 위한 최소 이동 수를 공백을 기준으로 구분하여 출력한다.
단, 출력할 때는 입력 시에 상대편 말 정보가 주어졌던 순서에 맞게 차례대로 출력한다.
코드
from collections import deque
move = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
n, m = map(int, input().split())
kx, ky = map(int, input().split()) # 나이트 위치
board = [[-1] * (n+1) for _ in range(n+1)] # 칸별로 도달하는데 필요한 말의 이동 횟수
q = deque([[kx, ky, 0]])
board[kx][ky] = 0
while q:
x, y, cnt = q.popleft()
for i in range(8):
nx = x + move[i][0]
ny = y + move[i][1]
if 1 <= nx <= n and 1 <= ny <= n and board[nx][ny] == -1:
q.append([nx, ny, cnt+1])
board[nx][ny] = cnt+1
for _ in range(m):
ex, ey = map(int, input().split()) # 상대편 말 위치
print(board[ex][ey])
처음에는 상대편 말의 위치를 입력받을 때마다 BFS를 수행하게 했더니 시간 초과가 발생하였다. 그래서 BFS를 한 번만 수행하며 나이트가 각 칸에 도달하는데 필요한 최소 이동 횟수를 저장해놓고 그 값을 출력하도록 하였더니 해결되었다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 21937번 작업 (0) | 2023.08.19 |
---|---|
[Python/파이썬] 백준 17090번 미로 탈출하기 (0) | 2023.08.17 |
[Python/파이썬] 백준 1520번 내리막 길 (0) | 2023.07.31 |
[Python/파이썬] 백준 3187번 양치기 꿍 (0) | 2023.07.21 |
[Python/파이썬] 백준 4179번 불! (0) | 2023.07.16 |