2차원 BFS

최단거리를 찾는 문제는 BFS로 해결할 수 있다.
2차원에서 BFS를 하는 방법은 다음과 같다.

1. Queue에서 현재 좌표를 얻는다.
   1.1. 현재좌표와 목표(좌표, 상태 등)가 같다면 종료한다.
2. 다음 좌표를 계산한다.
   2.1 방문한 적이 없다면 Queue에 삽입한다.
   2.2 이미 방문했다면 무시한다.
3. 1과 2를 반복한다.

일반적으로, 2차원 탐색은 다음과 같이 좌표가 이동한다.

방향벡터를 dx = [0, 0, 1, -1], dy = [1, -1, 0, 0], 현재 좌표를 (x, y), 다음좌표를 (nx, ny)라 하면

nx = x + dx[i], ny = y + dy[i] // next position

한편, 데스나이트 문제를 보면 좀 다르다.
BOJ 16948, 데스나이트

데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

따라서 다음 좌표를 구하기 위한 방향벡터는 다음과 같다.

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

# python code
N = int(input())

# board[][]는 visit[][]처럼 이용한다.
board = [[0] * (N) for _ in range(N)]
x1, y1, x2, y2 = input().split()
x1 = int(x1); y1 = int(y1); x2 = int(x2); y2 = int(y2);
dx = [-2, -2, 0, 0, 2, 2]
dy = [-1, 1, -2, 2, -1, 1]

q = [[x1, y1, 0]]
board[x1][y1] = 1
isFind = False

# 현재 (x, y)가 board위에 있을 수 있는지 확인하는 함수
def isHere(x, y):
    return x >= 0 and x < N and y >= 0 and y < N

while q:
    x = q[0][0]
    y = q[0][1]
    dist = q[0][2]
    del q[0]

    if x == x2 and y == y2:
        isFind = True
        break

    for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        if isHere(nx, ny) and board[nx][ny] == 0:
            q.append([nx, ny, dist + 1])
            board[nx][ny] = 1

# BFS 탐색이 끝난 후 출력 처리
if isFind:
    print(dist)
# 탐색을 다 했어도 도달할 수 없는 경우(해를 찾을 수 없는 경우)
else:
    print('-1')