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

 

풀이

 

• 현재 위치에서 나이트가 갈 수 있는 방향대로 이동하여 
• 이동 가능할 경우 해당 위치의 좌표와 이동 횟수를 함께 q에 넣으며,
• 방문 표시를 통해 재방문하지 않도록 하기!
• 그리고 check를 통해 초기 셋팅했던 상대편 말을 만났을 때 
• 1 증가 시키며, 결국 m과 같을 경우 완전한 종료를 하도록 만듦
• 이후 상대편 말의 위치에 대한 이동 수를 출력하여 해결.

 

import sys

from collections import deque

input = sys.stdin.readline

n,m = map(int,input().split())

mtx = [[0]*n for _ in range(n)]

visit = [[0]*n for _ in range(n)]

x,y = map(int,input().split())

result = []

for _ in range(m):

    a,b = map(int,input().split())

    mtx[a-1][b-1] = -1

    result.append([a-1,b-1])

visit[x-1][y-1] = 1

q = deque([[x-1,y-1,0]])

check = 0

while q:

    _x,_y,cnt = q.popleft()

    for dx,dy in [[_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]]:

        if 0<=dx<n and 0<=dy<n and not visit[dx][dy]:

            if mtx[dx][dy] == -1:

                check += 1

                mtx[dx][dy] = cnt+1

            if check == m:

                q.clear()

                break

            else:

                visit[dx][dy] = 1

                q.append([dx,dy,cnt+1])

for x,y in result: print(mtx[x][y], end=' ')