[BOJ / 백준] 16948 데스 나이트 python / 파이썬 bfs

출처 : https://www.acmicpc.net/problem/16948

16948번: 데스 나이트

---

1) 요구사항 분석 : 문제 읽기

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수

 

2) 설계 : 접근 방식

데스 나이트가 이동할수 있는 곳이 체스판 안에 있는지 확인하는 함수를 만들어줌

 bfs이용해서 풀어줌

 

bfs의 값이 false이면 -1 출력

# BOJ16948 데스 나이트
from collections import deque
que = deque()
n = int(input())
r1, c1, r2, c2 = map(int, input().split())

visited = [[False for _ in range(n)] for _ in range(n)]

di = [-2, -2, 0, 0, 2, 2]
dj = [-1, 1, -2, 2, -1, 1]

def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

def bfs():
    global ans
    global que
    while len(que) > 0:
        size = len(que)
        for i in range(size):
            tem = que.popleft()
            for i in range(6):
                ni = tem[0] + di[i]
                nj = tem[1] + dj[i]
                if in_range(ni, nj) and visited[ni][nj] == False:
                    visited[ni][nj] = True
                    que.append([ni, nj])
                    if ni == r2 and nj == c2:
                        return True
        ans += 1
    return False

ans = 0
que.append([r1, c1])
visited[r1][c1] = True

if r1 == r2 and c1 == c2:
    print(ans)
else:
    ans = 1
    if bfs():
        print(ans)
    else:
        print(-1)