[백준 7562번 파이썬 풀이] 나이트의 이동 알고리즘

2024.07.28 - [1일 1알고리즘] - 백준 1697번 숨바꼭질 문제 bfs 파이썬 풀이

 

 

너비 우선 탐색에 익숙하지 않은 분들은 위 링크 참고 부탁드리겠습니다.

 

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

test_case = int(input().strip())
for _ in range(test_case):
    l = int(input().strip())
    chase = [[0 for _ in range(l)] for _ in range(l)]
    sx, sy = map(int, input().strip().split())
    endx, endy = map(int, input().strip().split())
    tmp = deque()
    tmp.append((sy,sx))
    chase[sy][sx] = 1

    while tmp:
        y,x = tmp.popleft()
        if y == endy and x == endx:
            print(chase[y][x]-1)
            break
            
        for dy,dx in ((2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(1,-2),(2,-1)):
            ey = dy + y
            ex = dx + x
            if 0 <= ey < l and 0 <= ex < l and chase[ey][ex] == 0:
                chase[ey][ex] = chase[y][x] + 1
                tmp.append((ey,ex))
    else:
        print(0)

 

이상 너비 우선 탐색을 활용한 난이도가 낮은 bfs문제 풀이였습니다.

 

for문안에 나이트가 이동할 수 있는 경우의 수를 전부 넣어주고 각각 bfs를 돌려주면 됩니다.

chase[ey][ex] = chase[y][x] + 1

를 이용해 지금까지 온 거리를 계산해주고

마지막에 1을 빼서 시작할시에 이동하지도 않았는데 1이라고 써있는값을 빼주는 작업을 통해 정답이 출력됩니다.