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

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

7562번: 나이트의 이동

 

전에 푼 배추, 미로 응용 버전이었다.

단지 날뛰어 다니는게 더 멀리 폴짝폴짝 뛰는거 말곤 기본 BFS인듯하다.

 

 

근데 다 짜고 보니 체크 리스트를 굳이 저장을 안해도 될 듯하다. 만약 숫자가 있으면으로 체크하면 될 것 같은데 불필요한 리스트다.

그래도 보기 좋으니까 넘어간다.

from collections import deque
n = int(input())

dx = [1, 1, -1, -1, 2, 2, -2, -2]
dy = [2, -2, 2, -2, 1, -1, 1, -1]
for i in range(n):
    m = int(input())
    dis = [[0 for _ in range(m)] for i in range(m)]
    ch = [[0 for _ in range(m)] for i in range(m)]

    x, y = map(int, input().split())
    goal_x, goal_y = map(int, input().split())

    ch[x][y] = 1
    dis[x][y] = 0

    dq = deque()
    dq.append((x, y))

    while dq:
        now_x, now_y = dq.popleft()

        if now_x == goal_x and now_y == goal_y:
            print(dis[now_x][now_y])
            break

        for j in range(8):
            nx = now_x + dx[j]
            ny = now_y + dy[j]

            if 0<=nx<m and 0<=ny<m:
                if ch[nx][ny] == 0:
                    ch[nx][ny] = 1
                    dis[nx][ny] = dis[now_x][now_y] + 1
                    dq.append((nx, ny))

 

완성