BOJ 7562 - 나이트의 이동

folder_open Algorithm / BOJ / silver | date_range last modified at / created at 16 Oct 2024

sell #BOJ #7562 #silver #python #파이썬 #코딩테스트 #알고리즘

맨 위로

• 문제 링크
• 구현
• 코드

문제 링크

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

구현

BFS문제이다. 다만, 노드의 추가를 나이트가 이동하는 과정으로 추가하면 된다.
시간이 1788ms가 나왔는데, 맞힌 사람들의 시간을 보니 훨씬 시간이 적게 나왔다. 확인해보니, 목표좌표가 l보다 작으면 보드를 잘라주는 등 BFS의 노드탐색을 줄이기 위한 방법을 적용한 것 같다.

코드

from sys import stdin
from collections import deque
input = lambda : stdin.readline()


def main():
    t = int(input())
    moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (-1, 2), (-1, -2), (1, 2), (1, -2)]
    for _ in range(t):
        l = int(input())
        curr = tuple(map(int, input().split()))
        target = tuple(map(int, input().split()))
        
        queue = deque()
        visited = set()
        queue.append((curr, 0))
        visited.add(curr)
        while queue:
            node = queue.popleft()
            if node[0] == target:
                print(node[1])
                break
            for i in moves:
                new_x, new_y = node[0][0] + i[0], node[0][1] + i[1]
                if 0 <= new_x < l and 0 <= new_y < l:
                    if (new_x, new_y) not in visited:
                        queue.append(((new_x, new_y), node[1] + 1))
                        visited.add((new_x, new_y))

if __name__ == '__main__':
    main()