[백준/Python3] 7562 나이트의 이동

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

---

풀이

나이트가 현재 위치에서 목표 위치로 도달할 때까지 걸리는 최소 이동횟수를 구하는 문제다. BFS를 이용해 간단히 해결할 수 있다.

l*l 만큼의 리스트를 만들고 이를 방문했다면 True, 아직 방문하지 않았다면 False로 둔다.

if MAP[i][j] == False: 
	# (i, j)를 아직 방문하지 않음
elif MAP[i][j] == True:
	# (i, j)는 이미 방문했었음

현재 위치에서 나이트가 이동할 수 있는 좌표 중 아직 방문하지 않은 좌표를 queue에 넣는다. 이때 좌표가 목표 좌표와 같다면 탐색을 종료한다.

코드

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

knights = [[-2, 1], [-1, 2], [1, 2], [2, 1],
            [-2, -1], [-1, -2], [1, -2], [2, -1]]

def solution(l, start_x, start_y, target_x, target_y):
    MAP = [[False for _ in range(l)] for _ in range(l)] # visited table
    MAP[start_x][start_y] = True
    queue = deque()
    answer = 0
    ret = deque()
    ret.append(answer)

    if start_x == target_x and start_y == target_y:
        return answer

    # 처음 위치 넣기
    cnt = ret.popleft()
    for move in knights:
        temp_x = start_x + move[0]
        temp_y = start_y + move[1]

        if 0 <= temp_x < l and 0 <= temp_y < l and not MAP[temp_x][temp_y]:
            queue.append([temp_x, temp_y])
            MAP[temp_x][temp_y] = True
            ret.append(cnt+1)

    answer = 1
    while(queue):
        node = queue.popleft()
        cnt = ret.popleft()

        # print(f'[DEBUG] now x: {node[0]}, y: {node[1]}')
        if node[0] == target_x and node[1] == target_y:
            return cnt

        for move in knights:
            temp_x = node[0] + move[0]
            temp_y = node[1] + move[1]

            if 0 <= temp_x < l and 0 <= temp_y < l and not MAP[temp_x][temp_y]:
                queue.append([temp_x, temp_y])
                MAP[temp_x][temp_y] = True
                ret.append(cnt+1)



# Initial
for _ in range(int(input())):
    l = int(input())
    start_x, start_y = map(int, input().split())
    target_x, target_y = map(int, input().split())
    print(solution(l, start_x, start_y, target_x, target_y))