글 읽기 - 파이썬 bfs탐색의 방문체크와 시간초과에 관하여

yiyun11 1년 전 0

1번 코드는 단순 list에 본 위치의 정보가 있는지 없는지를 이용하여 방문체크를 한 코드이고,

2번 코드는 다른 분들의 코드에서 아이디어를 얻어 3차원 리스트를 이용하여 방문체크를 한 코드입니다.

이외에 다른 부분은 동일하며, 두 코드 모두 제가 아는 케이스에 한해서 정상적으로 작동합니다.

그런데 1번 코드는 시간초과가 뜨고 2번 코드는 pass를 받았습니다. 그 실행시간의 차이도 심한듯 합니다.

혹시 왜 이같은 차이가 발생하는 걸까요?

list에 값이 있는지 없는지 찾는 시간이 3차원 리스트에 인덱스로 접근하는 시간보다 오래걸려서 그런건가요?

정확한 이유를 알고 싶습니다.

# 1 (지도는 li에 저장되어있습니다)
def bfs(x,y):
    q = deque()
    q.append([x,y, False, 1]) # 3번째 인수는 벽을 깬 여부, 4번째는 distance
    visited = [[x,y, False]] # 단순 리스트로 방명록
    while q:
        x, y, w, d = q.popleft()
        if x==m-1 and y==n-1:
            return d
        
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<m and 0<=ny<n and ([nx, ny, w] not in visited):
                if li[ny][nx]==0:
                    visited.append([nx,ny, w])
                    q.append([nx,ny, w, d+1])
                elif w==False:
                    visited.append([nx,ny, True])
                    q.append([nx, ny, True, d+1])
                    
    return -1

# 2
def bfs(x,y):
    q = deque()
    q.append([x,y, 0]) # 3번째 인수는 벽을 깼는지 여부
    visited = [[[False]*2 for _ in range(m)] for _ in range(n)] # 3차원리스트로 방명록
    visited[0][0][0] = 1
    while q:
        x, y, w = q.popleft()
        if x==m-1 and y==n-1:
            return visited[y][x][w]
    
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<m and 0<=ny<n and (not visited[ny][nx][w]):
                if li[ny][nx]==0:
                    visited[ny][nx][w]=visited[y][x][w]+1
                    q.append([nx,ny, w])
                elif w==0:
                    visited[ny][nx][1]=visited[y][x][w]+1
                    q.append([nx, ny, 1])
                    
    return -1

luniro 1년 전 1

네 맞습니다 3차원 배열이면 O(1)의 시간복잡도로 방문여부 확인이 가능하지만 #1같은 경우는 최악의 경우 거의 매번 리스트 전체를 순회하게 됩니다

pezlunakr 1년 전 2

파이썬의 in 연산은 기본적으로 선형 탐색입니다.

따라서 가장 앞의 값부터 순회하며 검사하기에, 최악의 경우 O(N)이 걸리게 됩니다.

반면, 인덱스를 통해 바로 접근하는 방식은 순회나 탐색을 하지 않고 직접 메모리 주소를 참조하기 때문에 O(1)입니다.

aksndk123 1년 전 2

1번처럼 사용하고 싶으면 visit을 리스트가 아닌 set으로 두고 value를 리스트가 아닌 튜플로 사용해서 사용하면 됩니다.

이론상 set에서 in연산은 O(1)의 시간복잡도를 가지니까요.

ex)

visited = set()

visited.add((0,0,0))

비슷한 방식으로 from collections import defaultdict 을 사용해서 defaultdict형식의 key값을 튜플로 사용해서 visit 체크를 할수도 있습니다.

ex)

visit = defaultdict(int) # 기본적으로 모든 key값에 대해서 value의 초기값으로 0을 가짐
visit[(0,0,0)] = 1

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

문제

문제

출처

ICPC

파이썬 bfs탐색의 방문체크와 시간초과에 관하여

yiyun11 1년 전 0

luniro 1년 전 1

pezlunakr 1년 전 2

aksndk123 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말