글 읽기 - 파이썬 단순 bfs 구현인데 시간초과가 나는 이유가 뭘까요?

ray5273 3년 전 0

C++ 로 해결한 문제를 파이썬으로 바꿔서 풀어보려고 하였습니다.

어디서 시간초과가 생긴건지 잘 모르겠어서 질문드립니다.

단순한 bfs 구현인데, 시간초과가 어떻게 뜨는건지 잘 모르겠네요

도움이 필요합니다.

from collections import deque
import sys


def bfs(x1,y1,x2,y2,visited,path):

    q = deque()
    cost = deque()
    dx = [-1,0,0,1]
    dy = [0,1,-1,0]
    visited[x1][y1]=True
    q.append((x1,y1))
    cost.append(0)

    while q:
        cur = q.popleft()
        cur_x = cur[0]
        cur_y = cur[1]
        cur_cost = cost.popleft()
        # print(cur_x,cur_y)
        if cur_x == x2 and cur_y == y2:
            return cur_cost
                                              
        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]
            if next_x>=0 and next_y>=0 and next_x<=n and next_y<=m and visited[next_x][next_y] == False:
                q.append((next_x,next_y))
                cost.append(cur_cost+1)
                visited[next_x][next_y]=True
                path[next_x][next_y]= (cur_x,cur_y)
    return -1


def get_dist(a1x,a1y,a2x,a2y,b1x,b1y,b2x,b2y):
    visited = [[False for _ in range(101)] for _ in range(101)]
    path = [[(0, 0) for _ in range(101)] for _ in range(101)]
    visited[b1x][b1y] = True
    visited[b2x][b2y] = True
    dist_aa1 = bfs(a1x, a1y, a2x, a2y,visited,path)

    visited = [[False for _ in range(101)] for _ in range(101)]

    cur_x = a2x
    cur_y = a2y
    while True:
        visited[cur_x][cur_y] = True
        if cur_x == a1x and cur_y == a1y:
            break
        x = path[cur_x][cur_y][0]
        y = path[cur_x][cur_y][1]
        cur_x = x
        cur_y = y

    dist_aa2 = bfs(b1x, b1y, b2x, b2y,visited,path)
    return dist_aa1,dist_aa2

if __name__ == "__main__":
    m,n = map(int,sys.stdin.readline().split())
    a1x,a1y = map(int,sys.stdin.readline().split())
    a2x,a2y = map(int,sys.stdin.readline().split())
    b1x,b1y = map(int,sys.stdin.readline().split())
    b2x,b2y = map(int,sys.stdin.readline().split())

    
    dist_aa1, dist_aa2 = get_dist(a1x,a1y,a2x,a2y,b1x,b1y,b2x,b2y)
    # print(dist_aa1,dist_aa2)
    ans1 = 0
    if dist_aa1 == -1 or dist_aa2 == -1:
        ans1 = -1
    else:
        ans1 = dist_aa1 + dist_aa2

    dist_bb1, dist_bb2 = get_dist(b1x,b1y,b2x,b2y,a1x,a1y,a2x,a2y)
    # print(dist_bb1,dist_bb2)
    ans2 = 0
    if dist_bb1 == -1 or dist_bb2 ==-1:
        ans2=-1
    else:
        ans2 = dist_bb1 + dist_bb2

    if ans1 == -1 and ans2 == -1:
        print("IMPOSSIBLE")
    else:
        if ans1==-1:
            print(ans2)
        elif ans2==-1:
            print(ans1)
        else:
            print(min(ans1,ans2))

ray5273 3년 전 0

a1x,a1y = map(int,sys.stdin.readline().split())

a2x,a2y = map(int,sys.stdin.readline().split())

b1x,b1y = map(int,sys.stdin.readline().split())

b2x,b2y = map(int,sys.stdin.readline().split())

이부분을 잘못 구현했네요.

n,m 순서도 바꿔서 받으면 뒤에 나오는 A1,A2,B1,B2의 xy도 거꾸로 받아야하는데 여기서 거꾸로 받지 않았습니다.

a1y,a1x = map(int,sys.stdin.readline().split())

a2y,a2x = map(int,sys.stdin.readline().split())

b1y,b1x = map(int,sys.stdin.readline().split())

b2y,b2x = map(int,sys.stdin.readline().split())

이렇게 바뀌어야 맞습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 단순 bfs 구현인데 시간초과가 나는 이유가 뭘까요?

ray5273 3년 전 0

ray5273 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말