[Algorithm] 백준 16948 데스나이트 python

백준 데스나이트 원문

1. 문제가 뭐였지

뭐 어떻게 가면 된다는데 관심은 없고 점에서 점으로 이동하는 최소 이동횟수를 구해보잔다. 착하게도 행과 열이 0부터 시작한다.

2. 어떻게 풀었지

그냥 조건대로 bfs 돌리면 됨.

3. 어디서 해맸지

딱히 기억나는게 없어서 뭐지 하면서 코드를 다시 봤는데도 특별히 더 볼 건 없었다.

4. code

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

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

def solve(n,x,y,endx,endy) :

    board = [[-1 for i in range(n)] for i in range(n)]
    visit = [[False for i in range(n)] for i in range(n)]
    

    board[x][y] = 0
    visit[x][y] = True

    q = deque()

    q.append((x,y))

    while q :

        front = q.popleft()

        for i in range(6) :            
            newx = front[0] + dx[i]
            newy = front[1] + dy[i]

            if not (0 <= newx < n and 0<=newy<n) :
                continue
            
            if visit[newx][newy] == True :
                continue

            visit[newx][newy] = True
            board[newx][newy] = board[front[0]][front[1]]+1
            q.append((newx,newy))
    
    print(board[endx][endy])
    

if __name__ == "__main__" :
    
    n = int(input())

    x,y,endx,endy = map(int,input().split())

    solve(n,x,y,endx,endy)