🟩 [백준] [Python] [BFS/DFS] 7562번_나이트의 이동

문제

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

7562번: 나이트의 이동

풀이

먼저 BFS로 풀었을 때 시간초과가 나서 pypy3로 확인해봤더니 성공하였다. 

왜 시간초과가 났는지 곰곰히 생각해보면서 시간복잡도를 계산해보고 연산을 최소화 시키도록 코드를 바꾸었다.

# 백준 7562번 문제 - 나이트의 이동
from collections import deque
import sys
input = sys.stdin.readline
dx = [1,1,-1,-1,2,2,-2,-2]
dy = [2,-2,2,-2,1,-1,1,-1]
t = int(input())
def bfs(cur_x, cur_y):
    queue = deque()
    queue.append((cur_x, cur_y))
    while queue:
        x, y = queue.popleft()
        if x == move_x and y == move_y:
            print(graph[x][y])
            break
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < l and 0 <= ny < l and graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
for _ in range(t):
    l = int(input())
    graph = [[0]*(l) for _ in range(l)]
    cur_x, cur_y = map(int, input().split())
    move_x, move_y = map(int, input().split())
    bfs(cur_x, cur_y)

 

 

나의 처음 풀이

# 백준 7562번 문제 - 나이트의 이동
from collections import deque
import sys
dx = [1,1,-1,-1,2,2,-2,-2]
dy = [2,-2,2,-2,1,-1,1,-1]
t = int(input())
def bfs(cur_x, cur_y):
    queue = deque()
    queue.append((cur_x, cur_y))
    while queue:
        x, y = queue.popleft()
        
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= l or ny < 0 or ny >= l:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = 1
                visited[nx][ny] = visited[x][y] + 1
                queue.append((nx, ny))
            if graph[nx][ny] == 2:
                graph[nx][ny] = 1
                visited[nx][ny] = visited[x][y] + 1
for _ in range(t):
    l = int(input())
    graph = [[0]*(l) for _ in range(l)]
    visited = [[0]*(l) for _ in range(l)]
    cur_x, cur_y = map(int, input().split())
    move_x, move_y = map(int, input().split())

    graph[move_x][move_y] = 2
    if cur_x == move_x and cur_y == move_y:
        print(0)
    else:
        bfs(cur_x, cur_y)
        print(visited[move_x][move_y])