글 읽기 - 파이썬 BFS 구현시 시간초과 질문드립니다. (주석있음)

black01676 1년 전 0

간단하다고 생각하고 구현했는데

바로 시간초과 뜨게 되더라구요...

혹시 개선해야할 지점 있으면 가르침부탁드리겠습니다!

R, C = map(int, input().split())
arr = []
for i in range(R) :
    arr.append(input())

def bfs() :
    global Vmax
    q = [(0,0,{arr[0][0]},1)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while q :
        cx, cy, visit, cnt = q.pop(0)   #(cx,cy) : 현재 위치 , visit : 방문한 알파벳 set, cnt : 현재까지 온 횟수
        for i in range(4) :
            nx, ny = cx+dx[i], cy+dy[i]
            if 0<=nx<R and 0<=ny<C and arr[nx][ny] not in visit :   #그래프 범위 안에 있고 방문한적 없을 때
                Vmax = max(cnt+1, Vmax)   #가장 긴 Path update
                q.append((nx,ny,visit|{arr[nx][ny]},cnt+1))
    return
Vmax = 1
bfs()
print(Vmax)

pill27211 1년 전 1

파이썬은 잘 모르지만.. 중복된 알파벳 제거를 위해 set을 써보는 게 어떨까요 ? 리스트를 대상으로 in을 하는 것과 set을 대상으로 in을 하는 것은 차이가 꽤 날 것 같아요.

black01676 1년 전 0

도움말씀 감사드립니다! 저도 댓글주신거보고 아차 싶었는데

아마 시간은 무조건 줄었을거같은데 여전히 시간초과가 나네요 ㅠㅠ

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

문제

문제

출처

ICPC

파이썬 BFS 구현시 시간초과 질문드립니다. (주석있음)

black01676 1년 전 0

pill27211 1년 전 1

black01676 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말