글 읽기 - 파이썬 고수님들 이게 왜 시간초과나는지 모르겠어요 도와주세요

tlagmlwns12 3년 전 0

백준 미로탐색 bfs사용해서 풀어보려고 한건데 시간초과가 도대체 왜 나는지 모르겠어요 도와주세요 ㅠㅠ

from collections import deque as dq
n, m = map(int,input().split())
graph = [list(map(int,input().strip())) for _ in range(n)]

q = dq()

def bfs():
    q.append([0,0,0])
    visit = []
    while q:
        cnt,p1,p2 = q.popleft()
        if [p1,p2] not in visit:visit.append([p1,p2])
        for a, b in [-1,0],[0,1],[1,0],[0,-1]:
            ax, ay = p1+a, p2+b
            if 0 <= ax < n and 0 <= ay < m:
                if [ax,ay] in visit:continue
                if graph[ax][ay] == 1:
                    if ax == n-1 and ay == m-1:
                        cnt += 1
                        return print(cnt + 1)
                    q.append([cnt + 1,ax,ay])
    return print(-1)

bfs()

ploffer11 3년 전 1

visit이 너무 비효율적입니다.

기본적으로 리스트에서 in 연산자는 선형비교일 수밖에 없기 때문에 리스트의 크기에 시간복잡도가 의존합니다.

visit이 커짐에 따라 visit체크하는 부분의 시간복잡도가 O(nm)이 되므로 느릴 수 밖에 없습니다.

visit을 이차원 배열로 만들어 접근 시간을 O(1)로 하면 통과하지 않을까 생각이 드네요.

djm03178 3년 전 1

BFS는 큐에 원소를 삽입하기 전에 방문 표시를 해야 중복 방문을 막을 수 있습니다.

그리고 in은 리스트 전체를 순회해야 하기 때문에 현재 리스트 길이에 비례하는 시간이 걸리는 연산입니다.

tlagmlwns12 3년 전 0

고수님들 말씀하신데로 코드 해봤는데 이런식이 아닌가요

시간초과가 계속 나서,,,

from collections import deque as dq

q = dq()

n, m = map(int,input().split())
graph = [list(map(int,input().strip())) for _ in range(n)]

def bfs(g1,g2):
    visit = [[0]*m for _ in range(n)]
    q.append([1,0,0])
    while q:
        cnt, p1, p2 = q.popleft()
        visit[p1][p2] = cnt
        for a, b in [-1,0],[0,1],[1,0],[0,-1]:
            ax, ay = a + p1, b + p2
            if 0 <= ax < n and 0 <= ay < m:
                if graph[ax][ay] == 1 and visit[ax][ay] == 0:
                    if ax == (g1-1) and ay == (g2-1):return cnt+1
                    q.append([cnt + 1, ax,ay])
    return -1                 
           
print(bfs(n,m))

djm03178 3년 전 1

"BFS는 큐에 원소를 삽입하기 전에 방문 표시를 해야 중복 방문을 막을 수 있습니다."

를 처리하지 않으셨습니다.

tlagmlwns12 3년 전 0

감사합니닷 !

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

문제

문제

출처

ICPC

파이썬 고수님들 이게 왜 시간초과나는지 모르겠어요 도와주세요

tlagmlwns12 3년 전 0

ploffer11 3년 전 1

djm03178 3년 전 1

tlagmlwns12 3년 전 0

djm03178 3년 전 1

tlagmlwns12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말