[BOJ/Python] 7562_나이트의 이동

문제 출처:https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

문제

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

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

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

출력

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

예제 입력 1

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1

5
28
0

---

풀이

 

우선 코드는 다음과 같다.

 

import sys
import collections
 
move=[(2,1),(2,-1),(1,2),(1,-2),(-2,1),(-2,-1),(-1,2),(-1,-2)]
 
def bfs(l,start,end,visited):
    if start==end:
        return 0
 
    queue = collections.deque()
    queue.append(start)
    visited[start[0]][start[1]]=True
 
    count = 1
    distance = 1
 
    while queue:
        x,y = queue.popleft()
        count -=1
        for i in move:
            px = x+i[0]
            py = y+i[1]
 
            if 0<=px<l and 0<=py<l:
                if px==end[0] and py==end[1]:
                    return distance
                
                if visited[px][py]==False:
                    visited[px][py]=True
                    queue.append((px,py))
 
        if count==0:
            distance+=1
            count = len(queue)
 
 
t = int(sys.stdin.readline())
 
for _ in range(t):
    l = int(sys.stdin.readline())
    start = tuple(map(int,sys.stdin.readline().split()))
    end = tuple(map(int,sys.stdin.readline().split()))
    visited=[[False for _ in range(l)] for _ in range(l)]
 
    print(bfs(l,start,end,visited))

1. BFS를 이용하여 문제를 해결하였다.
2. move 리스트의 경우, 나이트가 현재 좌표에서 움직일 수 있는 8방향에 대한 dx와dy의 정보이다.
3. bfs 함수의 경우, 체스판의 크기와, 출발점과 도착점, 그리고 방문여부에 대한 리스트를 입력받는다.
4. 만약 출발점과 도착점이 같다면 이동을 안 해도 되므로 0을 return 한다.
5. 그게 아니라면 출발점을 큐에 넣고 방문표시를 해준다.
6. 큐에 원소가 존재하는 동안 반복한다.
7. move 리스트를 이용하여 현재 좌표를 기준으로 8방향을 탐색한다. (체스판 내부에 존재할 경우에 한하여 탐색한다.)
8. 만약 도착점을 찾는다면 distance를 return 한다.
9. 도착점은 아니지만 방문하지 않은 좌표라면 방문표시를 해주고 큐에 넣어준다.