[Python] 백준 7562번 - 나이트의 이동

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

7562번: 나이트의 이동

 

먼저 출발지, 도착지가 주어졌고 이 사이를 최소 몇 번만에 이동할 수 있는지 묻고 있기 때문에 BFS를 사용하면 적절하다는 것을 알 수 있다.

 

나이트 8방향에 대한 이동 코드는 다음과 같이 주었다.

dir = [[1, 2], [2, 1], [2, -1], [1, -2],
       [-1, -2], [-2, -1], [-2, 1], [-1, 2]]

 

이를 가지고 BFS를 적용해 풀었다.

이때, 처음에는 visited 변수를 list 형식으로 해야겠다고 생각했다.

그런데 만약 list를 사용하면 매번 방문 여부를 확인할 때 in연산 (O(n))을 사용해야하기 때문에 시간복잡도가 너무 높게 나올 것 같았다.

따라서 visited 변수를 matrix로 주고 not 연산(O(1))을 사용하도록 해주었다.

+) list 대신 set을 사용하면 동일한 in 연산이어도 O(1)의 시간이 소요되기 때문에, set으로 풀어봐도 될 것 같다. (https://jjung0326.tistory.com/66)

 

완성 코드는 다음과 같다.

from collections import deque

t = int(input())
dir = [[1, 2], [2, 1], [2, -1], [1, -2],
       [-1, -2], [-2, -1], [-2, 1], [-1, 2]]

def bfs(s, e):
    q = deque()
    q.append(s)
    visited = []
    for _ in range(l):
        visited.append([0]*l)
            
    while q:
        x, y = q.popleft()
        if x == e[0] and y == e[1]:
            return visited[x][y]
        for i in range(8):
            nx = x + dir[i][0]
            ny = y + dir[i][1]
            if 0 <= nx < l and 0 <= ny < l and not visited[nx][ny]:
                q.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1

for _ in range(t):
    l = int(input())
    start = list(map(int, input().split()))
    end = list(map(int, input().split()))
    
    count = bfs(start, end)
    print(count)