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

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

미로 찾기랑 비슷하다. 

저번에 탐색 문제 풀 때 bfs로 시간 초과가 뜬 경험을 삼아 dfs로 풀었는데 해결이 안 됐다.

생각해보다가 bfs로 풀었는데 바로 답이 나왔다.

내 생각에는 bfs니까 자연스럽게 최단거리가 나오니까(depth 별로 탐색) 이런 문제는 bfs로 푸는 게 좋은 거 같다.

 

풀이 과정

dx = [2,2,1,1,-1,-1,-2,-2]
dy = [1,-1,2,-2,2,-2,1,-1]

이런 식으로 나이트가 이동하는 좌표를 만들어두면 매우 편함.

 

나머지는 bfs를 알고 있으면 쉽게 문제를 해결할 수 있다.

 

 

전체 코드

from collections import deque
import sys

sys.setrecursionlimit(10**6)
dx = [2,2,1,1,-1,-1,-2,-2]
dy = [1,-1,2,-2,2,-2,1,-1]

T = int(input())

def bfs():
    deq = deque()
    deq.append([now_x,now_y])
    chesspan[now_x][now_y] = 1
    while deq:
        x,y = deq.popleft()
        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < L and 0 <= ny < L:
                if chesspan[nx][ny] == 0:
                    chesspan[nx][ny] = chesspan[x][y] + 1
                    deq.append([nx,ny])

for _ in range(T):
    L = int(input())

    chesspan = [[0 for _ in range(L)] for _ in range(L)]
    now_x, now_y = map(int,input().split())
    move_x, move_y = map(int,input().split())
    bfs()

    print(chesspan[move_x][move_y] - 1)

방문 확인은 따로 방문을 확인하는 리스트 없이 횟수를 저장하는 리스트로 해결했다.

맨 처음 시작하는 위치를 1로 하면 됨.

대신 이렇게 되면 모든 이동 횟수에 +1이 되니까 정답을 출력할 때 -1을 해준다.