[bfs/백준] 7562번 : 나이트의 이동

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

 

문제 이해 

- bfs의 기본 로직을 따르는 문제이고, 다른점은 움직이는 방향이 상하좌우 4가지가 아닌 대각선 방향으로 총 8가지의 움직임이 있다는 것이다. 

- 현재 있는 위치를 기준으로 움직이는 방향을 계산해서 directions 배열로 진행한다. 

 

풀이 로직 

- 전체 행렬 크기 n과 시작점 [a, b]와 도착지 [c,d]를 입력 받는다. 

- 방문여부를 확인과 몇 칸을 이용했는지 알기 위해 visit를 이용하는데, 시작점인 [a, b]의 visit 값은 1로 두고 시작한다. 

- visit 값이 0이면 방문하지 않은 지점이라 지나가면 되고, 1 이상이면 이미 방문한 지점이라 건너뛰면 된다. 

- while문으로 bfs를 진행하는데 도착한 지점이 목적지인 [c, d]라면 더 진행할 필요가 없으므로 루프를 break 한다. 
- 이전 지점에서 한 칸 움직이므로 visit[nx][ny] = visit[x][y] + 1로 설정한다.

- visit 행렬을 지나온 칸 수로도 사용하지만, 방문 여부로도 사용해서 정답값 + 1 형태이다. 그래서 visit[c][d] - 1을 출력한다. 

(시작점인 [a, b]에 있을 때 이동한 칸 수는 0이지만, visit[a][b] = 1 이기 때문)

 

정답 풀이 

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

directions = [[-2, -1], [-1, -2], [-2, 1], [-1, 2], [1, -2], [2, -1], [2, 1], [1, 2]]

for _ in range(int(input())):
    n = int(input())
    a, b = map(int, input().split())
    c, d = map(int, input().split())
    # [a, b] 에서 [c, d]로 몇 번 만에 가는지 
    
    queue = deque()
    queue.append([a, b])
    visit = [[0] * n for _ in range(n)]
    visit[a][b] = 1 
    while queue:
        x, y = queue.popleft()
        if x == c and y == d:
            break
        
        for i in range(8):
            nx, ny = x + directions[i][0], y + directions[i][1]
            if 0 <= nx < n and 0 <= ny < n:
                if not visit[nx][ny]:
                    visit[nx][ny] = visit[x][y] + 1
                    queue.append([nx, ny])
                    
    print(visit[c][d] - 1)