[Baekjoon] 16948 데스 나이트 python

🏷 문제

💡 코드

from sys import stdin
from collections import deque

def find(r1,c1,r2,c2):
    q = deque()
    q.append([r1,c1])
    graph[r1][c1] = 1
    case = [[-2,-1],[-2,1],[0,-2],[0,2],[2,-1],[2,1]]
    while q:
        r, c = q.popleft()
        if r == r2 and c == c2:
            # 처음을 1로 시작했기 때문에 -1
            return graph[r][c]-1
        for idx in range(6):
            newr, newc = r + case[idx][0],  c + case[idx][1]
            # 범위확인
            if 0<= newr < N and 0<= newc < N:
                if graph[newr][newc] == 0:
                    q.append([newr, newc])
                    graph[newr][newc] = graph[r][c] + 1
    return -1

N = int(stdin.readline())
r1, c1, r2, c2 = list(map(int, stdin.readline().split()))
graph = [[0] * N for _ in range(N)]
res = find(r1,c1,r2,c2)
print(res)

📌

기본적인 BFS 문제였다!
이동할 수 있는 경우를 case 리스트에 정의해두고, 시작 위치부터 시작해서 q가 빌 때 까지 포문을 계속해서 돈다!
pop한 값이 결과값과 일치할 때 그 값을 즉시 리턴하고, 만약 이동할 수 없다면, -1을 리턴한다 😃