[BOJ] 나이트의 이동

Minsu Han·2022년 12월 5일
0

알고리즘연습

목록 보기
58/105

코드

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

def bfs(sx, sy, dx, dy):
    q = deque([(sx, sy, 0)])
    visited[sx][sy] = 1
    while q:
        x, y, time = q.popleft()
        if x == dx and y == dy:
            return time
        for d in [(-2,-1), (-1,-2), (1,-2), (2,-1), (-2,1), (-1,2), (1,2), (2,1)]:
            nx, ny = x + d[0], y + d[1]
            if 0 <= nx < n and 0 <= ny < n:
                if not visited[nx][ny]:
                    visited[nx][ny] = 1
                    q.append((nx, ny, time+1))
    

t = int(input())
for _ in range(t):
    n = int(input())
    visited = [[0]*n for _ in range(n)]
    sx, sy = map(int, input().split())
    dx, dy = map(int, input().split())
    
    ans = bfs(sx, sy, dx, dy)
            
    print(ans)    # 정답 출력

결과

image


풀이 방법

  • 전형적인 bfs 문제이다.
  • 이미 비슷한 문제를 많이 풀어보았기 때문에 bfs 알고리즘 구현만 할 수 있다면 쉽게 풀 수 있었다.

profile
기록하기

0개의 댓글