bj7562 나이트의 이동

coh·2022년 6월 20일
0

백준

목록 보기
23/27

그냥 한번에 맞춰버려서 깜짝 놀라버림..
사실 지금까지 테스트케이스 돌리면서
에러가 안 뜬 적이 한번도 없는데
테스트 케이스가 한번에 깔끔하게 나와서 어? 해버림..

문제접근 방법

📍우선 BFS로 풀어야 되겠다고 생각했다. DFS는 잘못된 루트를 선택하는 순간 시간이 오래걸릴 것 같다는 생각이 듦.

📍나이트를 이동시켜주며 조건에 맞다면 deque에 넣고 횟수를 graph에 저장했다! 조건에 맞다면 break로 루프를 바로 빠져나오도록 함!

import sys
from collections import deque

n = int(input())


def bfs(graph, queue, goal, size):
    move = [(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2)]
    while queue:
        x, y = queue.popleft()
        if x == goal[0] and y == goal[1]:
            break
        for i in range(8):
            nx = x + move[i][0]
            ny = y + move[i][1]

            if 0 <= nx < size and 0 <= ny < size and graph[nx][ny] == 0:
                queue.append((nx,ny))
                graph[nx][ny] = graph[x][y] + 1



for _ in range(n):
    queue = deque([])
    size = int(input())
    graph = [[0] * size for _ in range(size)]
    cx, cy = map(int, sys.stdin.readline().split())
    queue.append((cx,cy))
    fx, fy = map(int, sys.stdin.readline().split())
    bfs(graph, queue, (fx, fy), size)
    print(graph[fx][fy])
profile
Written by coh

0개의 댓글