[백준/python] 16948번 데스 나이트 (bfs vs heapq)

1. 문제

 

이 문제는 데스 나이트라는 새로운 말이 이동할 수 있는 위치를 정의하여

시작 칸에서 도착 칸으로 이동하는 최소 이동 횟수를 구하는 문제다.

2. 풀이

지난주에 풀었던 7562번 나이트의 이동 문제와 비슷하다.

그 때는 bfs를 사용해서 문제를 해결했는데 다른 문제를 풀면서

heapq의 빠른 속도를 체감하고 새로운 방법으로 문제를 풀었다.

 

먼저 나이트가 움직일 수 있는 위치를 dx, dy 배열 안에 넣어준다.

move 함수를 만들어 방문 여부를 체크할 수 있는 배열과

우선순위 큐 적용을 위한 (cnt, r, c) 튜플을 넣은 배열을 만들어준다.

시작하는 위치의 방문여부를 True로 설정하고 다익스트라 알고리즘에 따라 코드를 짰다.

만약 도착 지점에 갔다면 cnt를 리턴해준다.

나이트가 갈 수 있는 모든 방향에 대해 이동이 가능한 경우 이동을 수행하고 방문여부를 참으로 바꾼다.

heapq.heappush를 사용하여 q에 (cnt+1, nx, ny) 튜플을 추가한다.

만약 모든 코드가 다 실행되는 동안 도착 지점에 가지 못하면 -1을 리턴하도록 하였다.

3. 코드

Heapq 사용

import sys
import heapq

input = sys.stdin.readline

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

def move(n, r1, c1, r2, c2):
    visited = [[False] * n for _ in range(n)]
    q = [(0, r1, c1)]
    visited[r1][c1] = True
    
    while q:
        cnt, r, c = heapq.heappop(q)
        if r == r2 and c == c2:
            return cnt
        
        for i in range(6):
            nx, ny = r + dx[i], c + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = True
                heapq.heappush(q, (cnt+1, nx, ny))
    return -1
        
n = int(input())
r1, c1, r2, c2 = map(int, input().split())
result = move(n, r1, c1, r2, c2)
print(result)

 

bfs 사용

 

from collections import deque
import sys

input = sys.stdin.readline

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

def move(n, r1, c1, r2, c2):
    visited = [[False] * n for _ in range(n)]
    q = deque([(0, r1, c1)])
    visited[r1][c1] = True
    
    while q:
        cnt, r, c = q.popleft()
        if r == r2 and c == c2:
            return cnt
        
        for i in range(6):
            nx, ny = r + dx[i], c + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((cnt+1, nx, ny))
    return -1
        
n = int(input())
r1, c1, r2, c2 = map(int, input().split())
result = move(n, r1, c1, r2, c2)
print(result)

4. 느낀 점

bfs와 heapq의 시간 차이를 확인하고자 두 코드를 모두 제출해보았다.

bfs는 72ms, heapq는 56ms가 나와 heapq의 속도가 더 빠름을 확인할 수 있었다.

 

이 문제를 통해 다익스트라 알고리즘에 좀 더 익숙해졌다.

앞으로 최단거리를 구하는 문제가 있을 때 다익스트라를 더 잘 활용해보자!

 

heapq.heappop(q)

heapq.heappush(q, (~~~))

기억하기!