[백준] 16948번 데스 나이트

💡문제접근

• BFS 완전탐색 유형의 문제
• chess[r2][c2]의 값이 0인 경우 이동할 수 없는 경우이므로 -1을 출력

💡코드(메모리 : 34176KB, 시간 : 80ms)

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

N = int(input())
chess = [[0] * N for _ in range(N)]
r1, c1, r2, c2 = map(int, input().strip().split())


def BFS(a, b):
    queue = deque()
    queue.append([a, b])
    while queue:
        r, c = queue.popleft()

        dr = [0, 2, 2, 0, -2, -2]
        dc = [-2, -1, 1, 2, 1, -1]
        for i in range(6):
            nr = r + dr[i]
            nc = c + dc[i]
            if nr < 0 or nr >= N or nc < 0 or nc >= N:
                continue
            if 0 <= nr < N and 0 <= nc < N and not chess[nr][nc]:
                chess[nr][nc] = chess[r][c] + 1
                queue.append([nr, nc])


BFS(r1, c1)
if chess[r2][c2] == 0:
    print(-1)
else:
    print(chess[r2][c2])

💡소요시간 : 21m