[DFS/BFS/완전탐색] 7562번 - 나이트의 이동(BFS)

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

풀이 시간: 15분 이내

 

1) 문제 해결 아이디어

시작 위치에서 목표 위치까지 최소 이동 횟수를 구하는 문제로 BFS로 풀 수 있는 대표적인 문제이다.

 

목표 지점에 도달하면 종료하는 코드는 사실상 없어도 정답이 되지만 있는 게 더 효율적이다.

해당 코드가 없으면 목표 위치에 도달하더라도 방문할 수 있는 좌표가 남아있다면 계속 탐색을 수행하기 때문이다.

 

<동작 과정>

1. 시작 지점 삽입, 방문 처리

2. 큐에서 좌표 하나 꺼내기

3. 2번에서 꺼낸 좌표 기준으로 8가지 방향 탐색

2-1. 범위 내이고 방문하지 않은 곳이면 삽입, 방문 처리

4. 목표 좌표가 될 때까지 2~3번 계속 반복

 

2) 소스코드

 

import sys
from collections import deque

# BFS
def bfs(x, y):
  queue = deque()
  # 시작 위치 삽입, 방문 처리
  queue.append((x, y))
  graph[x][y] = 1

  while queue:
    x, y = queue.popleft()
    # 목표 지점에 도달하면 종료
    if(x == endX and y == endY):
      break

    # 8가지 방향 탐색
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]

      if(0 <= nx < l and 0 <= ny < l):
        # 방문하지 않은 곳이면
        if graph[nx][ny] == 0:
          # 삽입, 방문 처리
          queue.append((nx, ny))
          graph[nx][ny] = graph[x][y] + 1     
  
# 위치 벡터
dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

t = int(sys.stdin.readline())  # 테스트 케이스 수
for _ in range(t):
  l = int(sys.stdin.readline())  # 체스판 길이
  startX, startY = list(map(int, sys.stdin.readline().split()))
  endX, endY = list(map(int, sys.stdin.readline().split()))
  graph = [[0] * l for _ in range(l)]  # l * l

  bfs(startX, startY)
  print(graph[endX][endY] - 1)