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

 7562번: 나이트의 이동

---

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

 

 

 

입력 :

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

 

출력 :

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

 

 

 

풀이)

목표 위치에 도달할때 까지 모든 경우의 수를 계산해야 하므로 처음에는 DFS를 생각했었다.

하지만 정답이 제대로 나오지 않았고, 검색을 통해  "최단 경로"의 경우에는 BFS를 쓰는 것이 맞다는 것을 알게 되었다.

처음에는 방문처리를 하지 않고 BFS를 돌렸는데, 어느정도 판이 커지게 되면 같은 구간을 계속해서 돌기 때문에

메모리 초과나 정답이 나오지 않았다.

 

처음 방문한 그 값이 제일 최단 거리라는 BFS의 특성을 이용하여, 방문시 해당 값을 그 자리에 할당하고, 그 뒤로는 방문하지 않는 식으로 코드를 짜서 정답을 맞추었다. 

정답 코드는 아래와 같다.

 

from collections import deque
 
def BFS(i, j):
    global g
    
    # 나이트의 이동 가능 위치
    di = [-1, -2, -2, -1, 1, 2, 2, 1] # 8방향
    dj = [-2, -1, 1, 2, 2, 1, -1, -2]
    
    queue = deque()
    queue.append([i, j])
 
    while queue:
        a, b = queue.popleft()
        
        # 목표위치 도달시 해당 위치의 값을 출력하고 함수를 끝냄
        if a == o and b == k:
            print(g[a][b])
            return
 
        for i in range(8):
            x = a + di[i]
            y = b + dj[i]
            if -1 < x < l and -1 < y < l and g[x][y] == 0:
                g[x][y] = g[a][b] + 1
                queue.append([x, y])
 
 
 
T = int(input())
for _ in range(T):
    l = int(input())
    g = [[0] * l for i in range(l)]
    
    # 출발 위치
    i, j = map(int, input().split())
    #목표 위치
    o, k = map(int, input().split())
    BFS(i, j)

 

 

이 문제를 풀면서 알게 된 것.

BFS의 경우 처음 도달하는 값이 제일 최단 경로가 된다.

 

---

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

7562번: 나이트의 이동