[BOJ 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

 

그래프에서 최단거리가 나왔다??

앞선 BFS와 DFS설명 글에서 설명했듯 BFS부터 생각하고 보면 된다.

 참고 : https://developbear.tistory.com/26 ✅

전형적인 BFS문제이고 심지어 한번만 BFS를 사용하면 되는 문제이다.

 

처음 BFS로 최단거리를 구해본다면 최단거리를 어떻게 구하지..? 라는 생각부터 들게될 것인데,

BFS의 특징을 다시 한번 자세히 생각해보면,

1.  너비 우선 탐색이다.
2.  처음 방문한 노드를 다시 방문하지 않는다.
3.  처음 방문한 노드가 가장 최단 거리이다.

정도이다. 즉, 그렇다면 초기값이 모두 0인 새로운 그래프를 만들고 (체스판과 동일한 크기의 그래프) 그곳에 노드를 방문할 때 마다 이전노드의 값 + 1 을 해주면 몇번의 이동을 했는지 쉽게 알 수 있다. 

→ 이미 방문한 노드는 다시 방문하지 않기 때문에 무조건 최단거리가 갱신된다.

 

이 생각까지 했다면, 이제 이 문제는 매우 쉽게 풀 수 있다.

체스말이 갈 수 있는 8가지 방향으로 BFS를 돌려주면 끝!

 

자세한 사항은 코드!!

 

from collections import deque
import sys


T = int(sys.stdin.readline().rstrip())

dx = [1,2,2,1,-1,-2,-2,-1]
dy = [-2,-1,1,2,2,1,-1,-2]

answer = []

for _ in range(T):
    N = int(sys.stdin.readline().rstrip())
    night = list(map(int,sys.stdin.readline().rstrip().split()))
    goal = list(map(int,sys.stdin.readline().rstrip().split()))

    visited = [[False for _ in range(N)] for _ in range(N)]
    board = [[0 for _ in range(N)] for _ in range(N)]
    
    if night[0] == goal[0] and night[1] == goal[1]:
        answer.append(0)
        continue

    queue =deque()
    queue.append([night[1],night[0]])
    board[night[1]][night[0]] = 0
    visited[night[1]][night[0]] = True
    result = 0
    while queue:
        #y,x
        check = False
        now = queue.popleft()
        for i in range(0,8):
            ny = now[0] + dy[i]
            nx = now[1] + dx[i]
            if ny >= 0 and ny < N and nx >= 0 and nx < N:
                if not visited[ny][nx]:
                    board[ny][nx] = board[now[0]][now[1]] + 1
                    if ny == goal[1] and nx == goal[0]:
                        result = board[ny][nx]
                        answer.append(result)
                        check = True
                    visited[ny][nx] = True
                    
                    queue.append([ny,nx])
        if check:
            break

for a in answer:
    print(a)

 

BFS를 연습하기에 매우 좋은 문제 같다😎

별다른 예외 처리도 없기 때문에 BFS를 처음 접한다면, 꼭 풀어보기를 권장한다✅

 

코드에 대한 다른 의견은 언제나 댓글 남겨주시면 감사하겠습니다!