[BOJ] 백준 7562 나이트의 이동

태환·2024년 2월 22일
0

Coding Test

목록 보기
80/151

📌 [BOJ] 백준 7562 나이트의 이동

📖 문제

📖 예제

📖 풀이

from collections import deque

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

def BFS(x, y):
  queue = deque()
  queue.append((x,y))
  while queue:
    x, y= queue.popleft()
    if x == ax and y == ay:
      break
    for i in range(8):
      nx = x+dx[i]
      ny = y+dy[i]
      if 0<=nx<I and 0<=ny<I and graph[nx][ny] == 0:
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx,ny))

T = int(input())
for _ in range(T):
  I = int(input())
  graph = [[0] * I for _ in range(I)]
  x, y = map(int, input().split())
  ax, ay = map(int, input().split())
  BFS(x,y)
  print(graph[ax][ay])

BFS를 활용하여 최단경로를 구하는 문제이며, 기존 문제들과의 차이는 나이트의 이용경로대로 dx와 dy를 설정해주는 것이다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글