[코테] 백준 BFS 16948번 문제

16948번 : 데스 나이트

문제 링크

https://www.acmicpc.net/problem/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)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

문제풀이

전형적인 BFS 문제로 방문하지 않던 곳들을 다 방문했어도 이동할 수 없는 경우에 -1을 출력한다.

from collections import deque

def bfs(_r, _c, _depth) :
    dy = [-2, -2, 0, 0, 2, 2]
    dx = [-1, 1, -2, 2, -1, 1]
    deq = deque([(_r, _c, _depth)])
    visited[_r][_c] = True
    
    while deq :
        print(deq)
        y, x, depth = deq.popleft()

        for i in range(6) : 
            ny, nx = y+dy[i], x+dx[i]

            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] :
                if [ny, nx] == [r2, c2] : 
                    return depth+1
                    
                deq.append((ny, nx, depth+1))
                visited[ny][nx] = True

    return -1
    
N = int(input())
r1, c1, r2, c2 = map(int, input().split())
visited = [[False for _ in range(N)] for _ in range(N)]
print(bfs(r1, c1, 0))