[백준] 16948번 데스 나이트 (python)

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

16948번: 데스 나이트

이 문제는 코드가 아쉬워서 계속 고쳤다. 제자리로 돌아온 것 같지만 기분 탓ㅎ

 

이 문제는 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구하는 것이다. 전형적인 bfs 문제로, 주어진 방향을 탐색하며 횟수를 더해가면 된다.

 

다른 bfs 문제와의 차별점을 찾자면 일반적인 상하좌우가 아니라, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1) 로 이동해야 한다는 것이다.

 

해결 방법은 아래와 같다.

 

1. 입력 받은 n을 토대로 n x n 체스판을 만들어준다.

2. 문제에서 제시한 좌표를 이용하기 위해 dx, dy를 정의한다.

3. 큐에서 시작 지점을 가져와 탐색을 시작한다.

4. 6가지 방향으로 탐색하며 목적지 좌표와 탐색 좌표가 일치할 경우, 해당 좌표의 이동 횟수를 출력하면서 함수를 종료한다.

5. 반복문이 종료되었음에도 불구하고 일치하는 목적지 좌표를 찾지 못하는 경우, -1를 반환하며 함수를 종료한다.

 

 

정답 코드

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

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

n = int(input())
r1, c1, r2, c2 = map(int, input().split())
graph = [[0] * n for _ in range(n)]

def bfs(x, y):
    dq = deque()
    dq.append((x, y))

    while dq:
        x, y = dq.popleft()

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

            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y]+1
                if nx == r2 and ny == c2:
                    return graph[r2][c2]
                dq.append((nx, ny))
                
    return -1

print(bfs(r1, c1))