백준 7562 - 나이트의 이동 Python

bfs를 이용한 기본적인 문제!

 

 

bfs를 완벽히 이해했다면

쉽게 풀릴문제이다.

 

8가지의 방향으로 이동하도록 구현하였다.

 

T = int(input())
from collections import deque
# q = []
# 방향
dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [-1, -2, -2, -1, 1, 2, 2, 1]

def bfs():
    visited = [[0 for _ in range(N)] for _ in range(N)]
    visited[stX][stY] = 1
    q = deque([(stX,stY)])
    while q:
        newX, newY = q.popleft()
        if newX == enX and newY == enY:
            return visited[newX][newY]

        for i in range(8):
            if 0<= newX+dx[i] <N and 0<= newY+dy[i] < N and visited[newX+dx[i]][newY+dy[i]] == 0:
                visited[newX + dx[i]][newY + dy[i]] = visited[newX][newY] + 1
                q.append((newX+dx[i], newY+dy[i]))
    return visited


for tc in range(1, T+1):
    N = int(input())

    stX, stY = map(int, input().split())
    enX, enY = map(int, input().split())

    print(bfs()-1)

처음에 deque 말고 그냥 리스트로 q.pop(0)을 했는데

시간초과가 떴다 ㅠㅠ

 

q에서 pop(0)하는 것은 시간복잡도가 O(n)이기 때문에

되도록 시간복잡도가 O(1)인 deque를 사용하는게 좋다!

 

 

희희