[백준_18404]_현명한나이트_python

https://www.acmicpc.net/problem/18404

18404번: 현명한 나이트

문제

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과 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)

단, 입력으로 주어지는 모든 말들의 위치는 중복되지 않으며, 나이트가 도달할 수 있는 위치로만 주어진다.

출력

첫째 줄에 각 상대편 말을 잡기 위한 최소 이동 수를 공백을 기준으로 구분하여 출력한다.

단, 출력할 때는 입력 시에 상대편 말 정보가 주어졌던 순서에 맞게 차례대로 출력한다.

문제 해결

현재 좌표에서 도착 좌표(상대 말)까지의 최단 방문 거리의 값을 구하는 문제이다. BFS 너비 우선 탐색으로 해결하면 된다.

nx, ny가 상대 노드인지 확인하는 것을 처리하는 과정을 O(1)로 끝낼 수 있는걸 *m이 되다 보니 N^2 * m이 되어 시간 초과가 발생했었다.

bfs를 한 번에 끝내도록 하고 상대 노드의 값을 구하는 과정을 간단히 하려 생각하면 쉽게 풀 수 있는 문제이다.

 

from collections import deque
import sys

def in_range(x,y):
    return 0<=x<n and 0<=y<n

def bfs():
    global n1,n2
    cnt = 0
    que = deque()
    que.append((n1,n2))
    visited[n1][n2] = 1
    while que:
        cnt += 1
        for _ in range(len(que)):
            a,b = que.popleft()
            for i in range(8):
                nx , ny = a+dx[i] , b+dy[i]
                if in_range(nx,ny) and not visited[nx][ny]:
                    visited[nx][ny] = visited[a][b]+1
                    que.append((nx,ny))
    return
input = sys.stdin.readline
n , m = map(int,input().split())
n1,n2 = map(int,input().split())
n1,n2 = n1-1,n2-1
dx,dy = [-1,-2,-2,-1,1,2,2,1],[-2,-1,1,2,-2,-1,1,2]
bt = []
visited = [[0] * n for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    bt.append((a,b))
ans = []
bfs()
for x,y in bt:
    ans.append(visited[x][y]-1)
print(*ans)