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

7562번: 나이트의 이동

from collections import deque

t = int(input())

dx = [-1,-2,-2,-1,1,2,2,1]
dy = [-2,-1,1,2,-2,-1,1,2]

for _ in range(t):

    n = int(input())

    start_x, start_y = map(int,input().split())
    dest_x, dest_y = map(int,input().split())

    visited = [[-1]*n for _ in range(n)]

    def bfs(x,y):
        
        visited[x][y] = 0
        
        queue = deque([(x,y)])

        while queue:
            
            curr_x,curr_y = queue.popleft()
            
            for i in range(8):
                nx = curr_x + dx[i]
                ny = curr_y + dy[i]

                if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == -1:
                    visited[nx][ny] = visited[curr_x][curr_y] + 1
                    queue.append((nx,ny))
    
    bfs(start_x,start_y)

    print(visited[dest_x][dest_y])

이번에는 8가지 방향으로 이동할 수 있는 나이트가 시작 지점(start_x, start_y)에서 시작하여 특정 지점(dest_x, dest_y)까지 이동할 수 있는 최소 이동 횟수를 구하는 문제이다.

 

최단 거리를 구해야하기 때문에 BFS 알고리즘을 사용했고, vistied 2차원 리스트를 T/F가 아닌 이동횟수로 저장하여 풀이할 수 있었다.

 

나 스스로 DFS/BFS 문제를 풀 때 명심해야 할 내용들을 정리해보았다.

1. 2차원 리스트를 탐색할 때는 무조건 방향을 저장하는 dx와 dy를 먼저 선언하자.
2. visited로 방문 여부를 확인하는 것을 잊지말자.
3. visited를 무조건 True/False로 저장하지말고, 필요하다면 다른 값으로 저장하자 !