[Algorithm][Python] 백준(BOJ) 16948

[문제]

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

---

풀이

[내 코드]

from collections import deque

def bfs(r,c):
    global r2, c2, count
    queue = deque();

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

    queue.append((r,c,0))
    visited.append((r,c))

    while queue:
        v = queue.popleft()

        if v[0] == r2 and v[1] == c2:
            print(v[2])
            return

        for i in range(6):
            nr = v[0] + dx[i]
            nc = v[1] + dy[i]

            if 0 <= nr < n and 0 <= nc < n:
                if (nr, nc) not in visited:
                   queue.append((nr, nc, v[2]+1))
                   visited.append((nr, nc))
                   
    print(-1)

n = int(input())
r1, c1, r2, c2 = map(int, input().split())

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

bfs(r1,c1)

💡 풀이

문제보고 bfs로 풀었는데 최소 이동 횟수를 어떻게 구하지?? 싶었다.
그래서 처음에 count 변수를 선언하고 queue에 append 될때마다 count+=1 을 했는데… 생각해보니 이 방식은 나이트가 갈 수 있는 모든 방법을 다 카운팅 해주는 거였다.

해결 방법은 queue에 넣어줄 때, 세번째 인자로
처음 (r2, c2, 0) 로 시작해서
(r2, c2, 0)으로 갈 수 있는 모든 방법은 (r, c, 1)로
그 다음으로 갈 수 있는 방법은 (r, c, 2)로 ~
1씩 올려서 카운팅 해주는 방식으로 하면 최소 이동 거리를 구할 수 있다.