[백준 18404번] 파이썬 - 현명한 나이트

백준 18404 - 현명한 나이트

시간 제한 1초, 메모리 제한 256MB

# 조건

• 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를 이용하여 풀어주면 된다.
• 주어진 크기의 arr을 생성한 후, 나이트를 1로, 상대 말을 2로 표시해준다.
• 또한, 주어진 상대방 말의 순서대로 출력해야 하므로,
  • result를 M 크기만큼 생성해주고,
  • record 딕셔너리에 주어진 말들의 인덱스를 key 값으로, 순서를 value로 사용하여 기록해준다.
• 나이트의 위치를 시작으로 bfs를 돌리며 visited의 값은 출발 위치 + 1로 기록해주고, 상대 말을 만난다면 딕셔너리에서 해당 말의 순서를 찾아서 result에 기록해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import defaultdict, deque  

def bfs(ci, cj):  
    q = deque()  
    q.append((ci, cj))  
    visited = [[-1] * N for _ in range(N)]  
    visited[ci][cj] = 0  
    while q:  
        si, sj = q.popleft()  
        if (si, sj) in record:  
            result[record[(si, sj)]] = visited[si][sj]  

        for d in range(8):  
            ni, nj = si+di[d], sj+dj[d]  
            if 0<=ni<N and 0<=nj<N and visited[ni][nj] == -1:  
                q.append((ni, nj))  
                visited[ni][nj] = visited[si][sj] + 1  

N, M = map(int, input().split())  
result = [0] * M  
record = defaultdict(int)  
arr = [[0]*N for _ in range(N)]  
ci, cj = map(int, input().split())  

arr[ci-1][cj-1] = 1  

for i in range(M):  
    a, b = map(int, input().split())  
    arr[a-1][b-1] = 2  
    record[(a-1, b-1)] = i  

di, dj = [-2, -2, -1, -1, 1, 1, 2, 2], [-1, 1, -2, 2, -2, 2, -1, 1]  
bfs(ci-1, cj-1)  
print(*result)