[Python] 백준 #18404- 현명한 나이트

문제

---

18404번: 현명한 나이트

코드

---

My answer

from collections import deque
from itertools import product
import sys
input = sys.stdin.readline

n, m = map(int, input().split())  # 판 크기, 상대편 수
x, y = map(int, input().split())  # 나이트 위치
visit = [[0]*(n+1) for i in range(n+1)]  # 방문 횟수 기록
target = []
dir = [[-2, -1], [-2, 1], [-1, -2], [-1, 2],
       [1, -2], [1, 2], [2, -1], [2, 1]]

def bfs(x, y):
    q = deque()
    q.append((x, y))
    visit[x][y] = 0

    while q:
        x, y = q.popleft()
        for i in dir:
            nowx, nowy = x+i[0], y+i[1]
            if (1 <= nowx <= n and 1 <= nowy <= n and visit[nowx][nowy] == 0):
                q.append((nowx, nowy))
                visit[nowx][nowy] = visit[x][y]+1

for i in range(m):
    target.append(list(map(int, input().split())))
bfs(x, y)
for i in target:
    print(visit[i[0]][i[1]])

Another answer

from collections import deque

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

# 모든 상대편 말의 위치를 저장
enemy = []
for i in range(m):
    a, b = map(int, input().split())
    enemy.append((a, b))

# 보드 전체를 -1으로 초기화
board = [[-1] * (n + 1) for _ in range(n + 1)]
# 나이트가 이동할 수 있는 8가지의 위치
dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [-1, 1, -2, 2, -2, 2, -1, 1]

# 현재 위치를 큐에 삽입
q = deque()
q.append((x, y))
# 현재 위치에 대한 최소 이동 수는 0
board[x][y] = 0

# 보드의 모든 위치에 대하여 최소 이동 수를 계산
while q:
    x, y = q.popleft()
    # 8가지 위치를 각각 확인
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        # 해당 위치로 이동할 수 있는 경우
        if 1 <= nx and nx <= n and 1 <= ny and ny <= n:
            # 방문한 적 없다면, 그 위치로의 최소 이동 수 계산
            if board[nx][ny] == -1:
                board[nx][ny] = board[x][y] + 1
                q.append((nx, ny))

# 모든 상대편 말까지의 최소 이동 수 출력
for a, b in enemy:
    print(board[a][b], end=' ')

풀이

---

최단 거리들을 찾아야하는 문제로 bfs를 통해 해결해야 했다.  

처음 시작위치를 나이트가 있는 위치로 지정해주고, 나이트가 움직일 수 있는 방향들을 모두 판을 벗어나지 않는 범위에 한하여 옮겨주며 현재 칸까지 움직인 횟수를 갱신해주면 됐다.