[백준7562&파이썬] BFS를 활용하여 최단거리에 도달하는 방법

# 문제

백준 7562 나이트의 이동 파이썬 풀이

7562번: 나이트의 이동

 

# 코드

import sys
from collections import deque

tc = int(sys.stdin.readline())

dirs = [
  (-2,1), (-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)
  ]


def solve() :
  l = int(sys.stdin.readline()) # 체스판의 한변의 길이 l * l
  visit = [ [False] * l  for i in range(l)]
  start = tuple(map(int,sys.stdin.readline().split())) # 현재 말의 위치
  target = tuple(map(int,sys.stdin.readline().split())) # 나이트가 가야할 위치
  dq = deque()
  dq.append( (start[0],start[1],0) ); visit[start[0]][start[1]] = True

  while len(dq) != 0 :
    cur = dq.popleft()
    # 현재 위치가 타겟이랑 같은지 확인
    if cur[0] == target[0] and cur[1] == target[1] :
      print(cur[2])
      return

    for dir in dirs :
      next = ( cur[0] + dir[0], cur[1] + dir[1], cur[2] + 1 )
      if 0<= next[0] < l and 0<= next[1] < l : # 이동이 체스보드안이라면
        if visit[next[0]][next[1]] == False : # 방문했던 곳이 아니라면
          #방문하기
          dq.append(next)
          visit[next[0]][next[1]] = True

          if next[0] == target[0] and next[1] == target[1]:
            print(next[2])
            return




for _ in range(tc) :
  solve()

 

# 풀이

## BFS를 이용하면 가중치가 없는 그래프의 최단거리 도달방법을 알 수있다.

• BFS는 너비우선탐색이기 때문에, 현재 위치에서 너비를 기준으로 한바퀴를 돈다. 이것을 하나의 사이클이라고 가정하고, 그 사이클의 단계를 기록해 놓는다면 몇번째 단계(사이클)만에 도달했는지를 알 수 있다.

dq.append( (start[0],start[1],0) ) # 3번째가 그 사이클의 단계를 기록한다.

next = ( cur[0] + dir[0], cur[1] + dir[1], cur[2] + 1 ) 이전 사이클에서 넘어온거기 때문에 +1 를 해준다

 

## 나이트는 시작부터 목적지에 도착 할 수 있다.

• 일단 문제의 조건에서 목적지에 도달하지 못하는 경우는 없다라는 별다른 말이 없기에 해당 케이스를 고려하지 않았다.
• 그러나 나이트가 시작부터 도착지에 있을 수도 있다 이런 케이스를 확인하기 위해서, deque에서 뽑자말자 한번 확인을 하고, next단계를 확인할때도 한번 더 확인하도록 했다. deque에서 뽑을때만 확인한다면, 큐에 넣을때도 도달헀는지를 충분히 알 수 있기 때문에 내 차례가 오기까지 매우 오래 걸릴 수 있기 때문이다.