[백준 파이썬] 7562 나이트의 이동

📌문제 출처

백준 단계별 문제풀이 - 그래프와 순회
https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

❓ 문제

❗ 풀이

• bfs 활용

📗 풀이 코드

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

def bfs(sta_y,sta_x): # 최초 위치(x,y)를 넣고 최소이동횟수를 반환하는 bfs 생성
    stack = deque([[sta_y,sta_x,0]])
    while stack :
        cur_y,cur_x,cnt = stack.popleft() # stack에서 현재 위치(x,y)와 이동횟수를 뽑아낸다.
        if [cur_y,cur_x] == [end_y,end_x]: # 도착했다면
            return cnt # 정답출력(이동횟수 오름차순으로 bfs이므로 처음 출력되는 값이 최소값이다)
        cnt += 1 # 현재 이동횟수 1 추가
        for i in range(8): # 나이트가 갈 수 있는 8개의 방향
            ny,nx = cur_y+dy[i], cur_x+dx[i]
            if (0<=ny<l) and (0<=nx<l) and (chk[ny][nx]==0): # 보드 위에 있고 처음가는 곳이라면
                stack.append([ny,nx,cnt]) # stack에 추가
                chk[ny][nx] = 1 # chk에 방문경험 초기화

dy = [-1,-2,-2,-1,1,2,2,1]
dx = [-2,-1,1,2,2,1,-1,-2]     
for _ in range(int(input())):
    l = int(input())
    sta_y, sta_x = map(int,input().split())
    end_y, end_x = map(int,input().split())
    chk = [[0]*l for _ in range(l)]
    print(bfs(sta_y,sta_x))

📗 코드 해설

• 최소이동횟수를 볼 것이므로 dfs보다는 이동횟수를 하나씩 올려가며 bfs로 보는 것이 효율적이다.
• bfs함수는 최초의 위치를 넣고 한번만 작동한다.
• stack에 최초의 위치와 이동횟수(최초니까 0)을 넣고 시작 칸으로 시작해서 stack에 이동할 수 있는 칸과 이동횟수를 하나씩 추가해주며 확인할 것이다.
• 나이트는 한 칸에서 총 8개의 칸으로 이동이 가능하므로 이동 가능한 모든 칸을 for 반복문으로 확인한다.
• 이때 새로운 위치는 체스판 위에 있어야하며,  이미 갔던 곳은 재방문이 불가능해야 시간을 단축할 수 있다.
  조건은 & 연산자가 아니라 and 연산자로 해주어야 하나의 if 조건문에서 앞에서부터 조건을 체크하고 뒤 조건을 체크하기 때문에 한 줄에서 연산이 가능하다.
• 이후 새로운 위치를 스택에 추가하고  새로운 이동하는 칸을 바로 방문했던 칸으로 초기화해준다.
• 최초로 도착지점에 다다른 순간 이동횟수를 출력해준다.