[백준 7562] 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

---

풀이

주어진 좌표간의 최단거리를 구하는데 이동할 수 있는 다음 좌표가 8개다

최단거리를 구해야하니 bfs를 사용하면 될 것 같고 이동할 수 있는 8개의 좌표는 사방탐색 방식으로 처리해주면 될 것 같다

그럼 팔방탐색이려나?

 

# 이동할 수 있는 8개의 좌표
dx = [1,2,2,1,-1,-2,-2,-1]
dy = [2,1,-1,-2,-2,-1,1,2]
move = 0
visited = []

먼저 8방탐색 좌표를 미리 깔아두고 테스트케이스가 여러개이므로 전역변수로 사용할 move와 visited를 선언한다

 

def bfs(start, end, l):
    q = deque()
    q.append(start)
    global move
    sx, sy = start
    ex, ey = end
    visited[sx][sy] = False # 시작좌표 check
    if sx == ex and sy == ey:   # 시작==도착인 경우
        return 0
    while q:
        L = len(q)  # 나이트가 한번 move할 때 큐에 담겨있는 노드를 한 싸이클로 체크
        move += 1
        for _ in range(L):
            cx, cy = q.popleft()
            for idx in range(8):
                nx = cx + dx[idx]
                ny = cy + dy[idx]
                if nx == ex and ny == ey:   # 다음 노드가 도착지일 경우
                    return move
                if 0 <= nx < l and 0 <= ny < l: # 좌표 범위 check
                    if visited[nx][ny]:
                        visited[nx][ny] = False
                        q.append([nx,ny])

 

 

for T in range(int(input())):
    l = int(input())
    sx, sy = map(int, input().split())
    ex, ey = map(int, input().split())
    visited = [([True]*l) for _ in range(l)]
    move = 0
    print(bfs([sx,sy], [ex,ey], l))