[백준] 7562번 - 나이트의 이동

참고: https://www.acmicpc.net/problem/7562

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

예제를 보면 반복할 횟수(테스트케이스)만큼 반복하면서

입력을 받고, 그 입력은 3줄로 주어지게 된다.

 

가장 처음 주어지는 값은 체스판의 크기 IxI가 되고,

그 다음은 현재 나이트가 있는 칸과 이동하려는 칸이 주어진다.

 

기존 그래프 문제와 다른 것은 나이트가 이동할 수 있는

방향에 대한 dy, dx의 설정값이라고 볼 수 있다.

 

made by 동쟁이

 

문제에 주어진 나이트의 이동을 x, y축 방향으로 좌표를 적어보았다.

x의 왼쪽은 음수, 오른쪽은 양수를 나타내고

y의 위쪽은 음수, 아래쪽은 양수를 나타낸다.

 

그러면 총 8가지의 좌표가 나오게 되고,

상하좌우의 4번 반복과는 다르게 총 8번의 반복을 진행하면서

숫자를 늘려가면 될 것이다.

 

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

t = int(input())
for _ in range(t):
  n = int(input())
  chs = [[0] * n for _ in range(n)]
  
  currY, currX = map(int, input().split())
  moveY, moveX = map(int, input().split())

  chs[currY][currX] = 1
  
  dy = [-2, -1, 1, 2, 2, 1, -1, -2]
  dx = [1, 2, 2, 1, -1, -2, -2, -1]

  def bfs(y, x):
    q = deque([(y, x)])
    while q:
      ey, ex = q.popleft()
      for k in range(8):
        ny = ey + dy[k]
        nx = ex + dx[k]
        if ey == moveY and ex == moveX:
          print(chs[moveY][moveX]-1)
          return
        if 0 <= ny < n and 0 <= nx < n and chs[ny][nx] == 0:
          chs[ny][nx] = chs[ey][ex] + 1
          q.append((ny, nx))
          
  bfs(currY, currX)

 

주어진 현재 좌표를 1로 기록하고,

1부터 시작하여 이동할 위치까지 수를 해당 위치에 +1만큼을 더해가면서

bfs의 큐를 반복하면 된다. 이때, 진행하는 현재 좌표가 이동할 위치와 같으면

함수를 탈출하면서 1부터 시작했기 때문에 이동할 위치에 있는 값에 -1을 해준다.

 

화이팅 💪