백준 7562번 - 나이트의 이동 - 파이썬(Python)

문제 링크

https://www.acmicpc.net/problem/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
from collections import deque
sys.setrecursionlimit(1000000)

def bfs(x,y):

    queue = deque([(x,y)])
    d = [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]
    visited = [[False]*n for _ in range(n)]
    visited[x][y] = True
    count = 0
    while queue:
        for _ in range(len(queue)):
            x,y = queue.popleft()

            if (x,y) == (a2,b2):
                print(count)
                return
            
            for i in range(8):
                nx,ny = (x,y) + d[i]
                if (0<=nx<n) and (0<=ny<n) and visited[nx][ny] == False:
                    queue.append((nx,ny))
                    visited[nx][ny]=True
        count+=1
              
t = int(input())

for _ in range(t):
    n = int(input())
    chess = [[0]*n for _ in range(n)]
    
    a1,b1 = map(int,input().split())
    a2,b2 = map(int,input().split())
    chess[a2][b2] = 1
    
    if (a1,b1) == (a2,b2):
        print(0)
    else:
        bfs(a2,b2)

예제 코드

import sys
from collections import deque

sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def bfs(x, y):
    queue = deque([(x, y)])
    d = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
    count = 0
    visited = [[False] * n for _ in range(n)]
    visited[x][y] = True

    while queue:
        for _ in range(len(queue)): 
            x, y = queue.popleft()

            if x == a2 and y == b2:
                print(count)
                return  
            
            for dx, dy in d:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                    queue.append((nx, ny))
                    visited[nx][ny] = True
        
        count += 1  

t = int(input())

for _ in range(t):
    n = int(input())  
    a1, b1 = map(int, input().split())  
    a2, b2 = map(int, input().split())  

    if (a1, b1) == (a2, b2):
        print(0)
    else:
        bfs(a1, b1)

 

 

생각

 

추후 정리