백준 7562번. 나이트의 이동 (Python / 파이썬)

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

---

문제 풀이

 체스판 위의 나이트가 한 번에 이동할 수 있는 칸은

문제에 제시된 그림에서 확인할 수 있습니다.

나이트가 이동하려고 하는 칸이 주어졌을 때

최소 몇 번만에 이동할 수 있는지 출력하는 문제입니다.

 

BFS 알고리즘을 이용해 문제를 해결했습니다. 

먼저 나이트의 이동 횟수를 저장할 2차원 list를 만들어주었고

Queue에 현재 나이트의 위치를 삽입해주었습니다.

 

Queue에서 삭제된 x, y의 위치에서 이동할수 있는 다음 위치를 탐색해주었습니다.

만약 다음 위치가 체스판 범위 안이고 아직 방문하지 않닸다면

현재 dist 값에 1을 더해 다음 위치의 dist 값을 갱신시켜주었습니다.

그리고 Queue에 다음 위치를 삽입해주었습니다.

 

이때, 주의해야 할 점은 만약 큐에서 삭제된 x, y를 확인하였는데

나이트가 이동하려는 위치라면 반복문을 종료해야한다는 것입니다.

반복문 종료 후 나이트가 이동하려는 위치에서의 dist 값을 출력하면

나이트가 이동하려는 위치까지 최소 몇번 이동해야하는지 출력할 수 있습니다.

---

My Code

from collections import deque

for tc in range(int(input())): # 테스트 케이스 개수만큼 반복
    n = int(input()) # 체스판의 한 변의 길이
    x, y = map(int,input().split()) # 현재 나이트의 위치
    t_x, t_y = map(int,input().split()) # 나이트가 이동하려고 하는 칸
 
    dist = [[0] * n for _ in range(n)] # 나이트의 이동 수를 저장할 list

    q = deque()
    q.append((x, y)) # 큐에 나이트의 현재 위치 삽입
    while q:
        x, y = q.popleft() # 큐에서 삭제된 x, y
        if x == t_x and y == t_y: # 만약 나이트가 이동하려고 하는 위치라면
            break                 # 종료
        # 나이트가 이동할 수 있는 다음 위치
        for nx, ny in ((x-2,y+1),(x-2,y-1),(x-1,y+2),(x-1,y-2),(x+2,y-1),(x+2,y+1),(x+1,y-2),(x+1,y+2)):
            if 0 <= nx < n and 0 <= ny < n: # 체스판 범위 안이고
                if dist[nx][ny] == 0:       # 아직 방문하지 않았다면
                    dist[nx][ny] = dist[x][y] + 1 # 현재 dist 값에 1을 더해 갱신
                    q.append((nx, ny))      # 큐에 다음 위치 삽입

    print(dist[t_x][t_y]) # 나이트가 이동하려 하는 위치에서의 dist 값 출력