[백준][Python] 7562번 나이트의 이동

[백준] 7562번 나이트의 이동

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

문제설명 📖

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

입력

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

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

출력

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

입출력 예

---

문제접근 💡

1. BFS구현 최단경로
2. 이동 가능한 좌표를 dx, dy로 설정해준다.(8방향)
3. 한 번 이동한 좌표의 값에 +1씩 해주며 이동한다.(2번 이동하면, 그 좌표값은 +1+1=2가 된다.)
4. 도착지 좌표에 방문하면 그 좌표의 값을 return한다.

문제풀이 💡

import sys
from collections import deque


t = int(input()) 

for _ in range(t):
    n = int(input())
    now = list(map(int, sys.stdin.readline().split()))
    dest = list(map(int, sys.stdin.readline().split()))   

    matrix = [[0]*n for _ in range(n)]
    visited = [[False]*n for _ in range(n)]

    queue = deque()
    
    # 시계방향
    dx = [-2, -1, 1, 2, 2, 1, -1, -2]
    dy = [1, 2, 2, 1, -1, -2, -2, -1]


    def bfs():
        queue.append(now)
        visited[now[0]][now[1]]

        while queue:
            x, y = queue.popleft()

            if x == dest[0] and y == dest[1] :
                return 0

            for i in range(8):
                nx = x+dx[i]
                ny = y+dy[i]

                if nx <0 or nx>=n or ny<0 or ny>=n:
                    continue

                if nx == dest[0] and ny == dest[1]:
                    visited[nx][ny] = True
                    return matrix[x][y]+1

                if visited[nx][ny] == False:
                    queue.append([nx,ny])
                    visited[nx][ny] = True
                    matrix[nx][ny] = matrix[x][y] + 1    
    
    answer = bfs()
    print(answer)

---

다른풀이 💡

로직은 같지만 while문을 써서 훨씬 더 간단하고 효율적으로 구현한 코드이다.
테스트 케이스를 받아서 여러번 입력받는 경우, while tc: , tc -=1을 사용해 코드를 구현하면 훨씬 간단하다.

from collections import deque

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

def bfs(x, y, x_end, y_end):
    q = deque()
    q.append([x, y])
    a[x][y] = 1
    while q:
        x, y = q.popleft()
        if x == x_end and y == y_end:
            return a[x][y]-1
        for i in range(8):
            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

tc = int(input())
while tc:
    l = int(input())
    a = [[0]*l for _ in range(l)]
    x1, y1 = map(int, input().split())
    x2, y2 = map(int, input().split())
    if x1 == x2 and y1 == y2:
        print(0)
        tc -= 1
        continue
    ans = bfs(x1, y1, x2, y2)
    print(ans)
    tc -= 1

출처 : https://chldkato.tistory.com/11