백준 7576 파이썬(bfs)

최단거리를 찾는 문제이므로 bfs탐색 알고리즘을 사용하면 쉽게 풀수 있다.

 

또 시간초과가 떳다.

이게 시간초과가 뜬 내가 만든 코드이고

from collections import deque
import sys
input = sys.stdin.readline
def bfs():
    while queue:
        x,y = queue.popleft()
        for step in range(8):
            nx,ny = x + dx[step], y+dy[step]
            if 0<=nx<i and 0<=ny<i and graph[nx][ny]== 0:  
                    queue.append((nx,ny))
                    graph[nx][ny] = graph[x][y]+1
# 7562 나이트의 이동
case = int(input())
# 나이트의 이동경로
dx = [-1,-2,-2,-1,1,2,2,1]
dy = [2,1,-1,-2,-2,-1,1,2]
for _ in range(case):
    i = int(input())
    a,b = map(int,input().split())
    c,d = map(int,input().split())
    graph = [[0]*i for _ in range(i)]
    queue = deque()
    queue.append((a,b))
    bfs()
    if (a,b) == (c,d):
        print(0)
    else:
        print(graph[c][d])

 

지금 이것은 구글에서 찾은 시간초과가 뜨지 않는 bfs탐색코드이다.

from collections import deque
import sys
input = sys.stdin.readline
dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]
def bfs(sx, sy, ax, ay):
    q = deque()
    q.append([sx, sy])
    s[sx][sy] = 1
    while q:
        a, b = q.popleft()
        if a == ax and b == ay:
            print(s[ax][ay] -1)
            return
        for i in range(8):
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < n and 0 <= y < n and s[x][y] == 0:
                q.append([x, y])
                s[x][y] = s[a][b] + 1
t = int(input())
for i in range(t):
    n = int(input())
    sx, sy = map(int, input().split())
    ax, ay = map(int, input().split())
    s = [[0] * n for i in range(n)]
    bfs(sx, sy, ax, ay)

 

몇번이나 두눈을 부릅뜨고 무엇이 차이일지 생각하면서 뜯어보았다.

변수를 지정하거나 큐 객체를 생성하는 순서만 조금의 차이가 있을 뿐 전체적인 아이디어와 구조는 두 코드 모두 같다고 생각한다.

무엇이 문제가 되어 시간초과를 만드는지 모르겠다.

정말 컴퓨터의 세계는 깊고 오묘한듯 하다.