[BFS] 나이트의 이동 (7562)

문제 설명

 

체스판 위에 한 나이트가 놓여 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다.

나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

입력

 

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다.

첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다.

둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

 

출력

 

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

---

문제 풀이

 

나이트의 이동 방향만 정확히 설정해주면 충분히 해결할 수 있다.

이동방향은 화살표를 기점으로 시계방향 순서로 나타내면 아래와 같다.

이제 BFS로 탐색하면서 목적지에 도착하면 횟수를 반환하면 된다.

그리고 방문체크를 하는 visit 배열을 선언하지 않고도 풀 수 있다. ➡︎ 방문한 좌표값을 이전 값에 +1을 시켜주면 된다.

 

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

t = int(input())

while t > 0:
  i = int(input())
  start = tuple(map(int, input().split())) # 시작 좌표
  end = tuple(map(int, input().split())) # 목적지 좌표
  graph = [[0 for _ in range(i)] for _ in range(i)]
  directions = [(-2,+1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)] #이동 방향
  answer = 0
  q = deque([start])

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

    if (x,y) == end:
      print(graph[end[0]][end[1]])
      break

    for j in range(8):
      dx, dy = x + directions[j][0], y + directions[j][1]
      if 0<=dx<i and 0<=dy<i: # 유효한 좌표 내에서만
        if graph[dx][dy] == 0:
          graph[dx][dy] = graph[x][y] +1 # 이동횟수 1씩 증가
          q.append((dx,dy))

  t-=1

 

---

후기

 

전형적인 BFS 문제여서 큰 어려움 없이 풀었다!

 

요즘 기업 코테를 보는 것마다 떨어져서 무엇이 문제일까 고민하고 여러 블로그도 참고하면서 기본기가 부족한 느낌을 받았다..😰

그래서 이번주부터 문제 유형별로 실버 단계부터 차근차근 풀고 있다.

무조건 어려운 문제를 풀 수 있다고 기업 코테에 붙는다는 보장이 없으니깐 기본기부터 확실히 하자! 💪