7. 백준 7562 (실버1) : 나이트의 이동 _ python풀이

문제

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

입력

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

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 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

---

 

*문제 해설

이 문제는 '자료구조'문제다. 그중에서 그래프 탐색관련 문제다.

BFS(너비 우선 탐색) 을 활용하여 문제를 풀면된다. 그 전에, 나이트의 움직임이 어떻게 되는지 좌표설정을 해줘야 한다. 총 8가지의 움직임을 취할 수 있다.

위 2	왼 1
위 2	오 1
위 1	왼 2
위 1	오 2
아래 2	왼 1
아래 2	오 1
아래 1	왼 2
아래 1	오 2

 

이런 8가지 움직임을 python에서 활용하기 위해 리스트로 저장하면 

dx = [ -1, 1, -2, 2, -1, 1, -2, 2 ]  # x축은 왼쪽 (-), 오른쪽 (+)

dy = [  2, 2, 1, 1, -2, -2, -1, -1 ] # y축은 위쪽 (+), 아래쪽 (-)

이제 이것을 가지고 코드를 작성하도록 하겠다.

 

*나의 코드

import sys
from collections import deque

dx = [ -1, 1, -2, 2, -1, 1, -2, 2 ]  # x축은 왼쪽 (-), 오른쪽 (+)
dy = [  2, 2, 1, 1, -2, -2, -1, -1 ] # y축은 위쪽 (+), 아래쪽 (-)

def bfs(x, y, x_end, y_end): #최소이동수 리턴
    q = deque() # bfs문제를 풀기위해 큐를 사용
    q.append([x,y]) # 최초 시작지점
    a[x][y] = 1                                # 이동횟수 기본 1으로 설정 ... (A)
    while q:                
        x, y = q.popleft()                     # 큐에 들어간거 빼내서 저장
        if x == x_end and y == y_end:          # 나이트가 목적지에 도달할 경우 이동횟수 리턴 후 종료
            return a[x][y]-1                   # (A)에서 1 설정된 만큼 빼주고 리턴
        for i in range(len(dx)):                    # 나이트의 움직임 종류 만큼 반복
            nx = x + dx[i]                      
            ny = y + dy[i]
            if 0 <= nx < l and 0 <= ny < l:    # 체스판 안에 나이트가 위치하며 최초이동지면 그 지역을 큐에 추가
                if a[nx][ny] == 0:             
                    q.append([nx, ny])
                    a[nx][ny] = a[x][y] + 1    # 배열 a에 (기존 이동 횟수) + 1 저장
# 큐는 나이트가 움직인 좌표를 저장하고 배열 a는 그 좌표에 도달하기까지의 이동횟수+1이 저장되어있다.        

test = int(input())
while test:
    l = int(input())
    a = [[0]*l for _ in range(l)]
    x1, y1 = map(int, sys.stdin.readline().split())
    x2, y2 = map(int, sys.stdin.readline().split())
    if x1 == x2 and y1 == y2:                  # 출발지와 도착지가 같은경우 0출력 후 test - 1
        print(0)
        test -= 1
        continue
    result = bfs(x1, y1, x2, y2)               # bfs로 최소이동횟수 탐색
    print(result)
    test -= 1

 

쉽지 않은 문제였다. python에 익숙하지않아 타입에러가 일어나는 등 여러 에러가 발생했다. 특히

for i in range(len(dx))

이 부분에서 len(dx)만 썼을 땐 타입에러가 일어나 for문이 제대로 작동하지않아 곤욕을 치뤘다. 리스트의 길이를 구해 for문에 사용할 땐 range()를 쓰는 습관을 들이도록 해야겠다.

 

 bfs의 작동방식은 dfs와 달리 한 우물만 깊게 파는 것이 아닌 갈 수 있는 길들을 다 가본 후 최초 위치에서 더 이상 갈 곳이 없을 때 가장 처음 이동한 곳에서 다시 탐색을 시작하는 것이 반복되는 것이다.

그걸 위해 for문을 통해 나이트가 이동할 수 있는 위치를 전부 큐에 저장했고 while문을 통해 for문을 반복해주었다.

 

별개로, a 는 [[0]*l for _ in range(l)] 을 통해 l * l 크기를 전부 0으로 채워주었다. 이러면 l이 3일 때 [0, 0, 0]이 3줄씩 생긴다.

---

*중요한 내용

bfs는 큐를 이용해 구현하고 while문과 for문을 이용해 작동하게 한다.