[백준] 7562 BFS 나이트의 이동 파이썬

https://www.acmicpc.net/problem/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

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = int(1e9)

def BFS():
    dx = [1,2,2,1,-1,-2,-2,-1]
    dy = [2,1,-1,-2,-2,-1,1,2]
    queue = deque()
    queue.append((row,col))
    graph[row][col] = 1
    while queue:
        v1, v2 = queue.popleft()
        if v1 == dest1 and v2 == dest2:
                return graph[v1][v2] - 1
                
        for i in range(8):
            nx = v1 + dx[i]
            ny = v2 + dy[i]
            if nx < 0 or ny < 0 or nx>=I or ny>=I:
                continue
            if graph[nx][ny] == 0:
             queue.append((nx,ny))
             graph[nx][ny] = graph[v1][v2] + 1

N = int(sys.stdin.readline().rstrip())
for _ in range(N):
    I = int(sys.stdin.readline().rstrip())
    graph = [[0] * I for _ in range(I)] # NxN 배열 선언
    row,col = map(int,sys.stdin.readline().split())
    dest1,dest2 =  map(int,sys.stdin.readline().split())
    print(BFS())

"최단"거리 

DFS로 풀게 되면 뭐 통과될수도는 있겠다(메모리 제한이 널널해서 일단 그렇게 생각은 했다)

근데 그렇게 되면 정말 "모든 노드"를 다 돌아야 해서 시간복잡도 면에서 불리함

최단거리 문제가 나오면 보통 BFS로 해결하려고 갈피를 잡는게 나은 것 같다.

 

 

아무리봐도 답이 맞는데 왜 안되나 봤더니

N이랑 I를 헷갈리고 있었다

문제에서 N은 테스트 케이스

I는 IxI에서의 행렬의 크기인데

바보같이 NxN이 익숙하니까 nx >=N or ny>=N

자꾸 테스트 돌려보면 3까지만 돌아가고 None이 돌아와서 

아오 뭐지,,, 하고 봤더니 I를 넣어야 하는 거였다니 ㅋㅋ

문자 정리를 잘하는 습관을 들여야겠다고 느끼는 하루였다