글 읽기 - 인구이동 파이썬 시간초과 질문 드립니다

cmg7111 5년 전 0

기본적으로 인구이동이 없을 때까지 while문을 돌리고, 
각 bfs는 for(for(bfs))식으로 돌립니다.
로직 자체에 문제가 있는건지 시간초과를 어떻게 해결할 지 모르겠네요 ㅜㅜ 조언 부탁드립니다.

​N,L,R=map(int,input().split())
map_lst=[]
for loop in range(N):
    map_lst.append(list(map(int,input().split())))

queue=[]
dy=[-1,0,1,0]
dx=[0,1,0,-1]

temp = [[0] * N for i in range(N)]
visited = [[0] * N for i in range(N)]
chk=1
res=-1
update=True
while update==True:
    update=False
    chk = 1
    for y_1 in range(N):
        for x_1 in range(N):
            if temp[y_1][x_1]:
                continue
            if visited[y_1][x_1]:
                continue
            queue.append([y_1,x_1])
            while queue:
                cur=queue.pop(0)
                visited[cur[0]][cur[1]] = 1
                for dir in range(0,4):
                    next_y=cur[0]+dy[dir]
                    next_x=cur[1]+dx[dir]
                    if 0<=next_y<N and 0<=next_x<N:
                        if visited[next_y][next_x]==0:
                            if L<=abs(map_lst[cur[0]][cur[1]]-map_lst[next_y][next_x])<=R:
                                update=True
                                temp[cur[0]][cur[1]]=chk
                                temp[next_y][next_x]=chk
                                queue.append([next_y,next_x])
            chk += 1

    union=[0]*N*N
    cnt=[0]*N*N
    for y in range(N):
        for x in range(N):
            if temp[y][x]!=0:
                union[temp[y][x]-1]+=map_lst[y][x]
                cnt[temp[y][x]-1]+=1

    for y_2 in range(N):
        for x_2 in range(N):
            if temp[y_2][x_2]!=0:
                map_lst[y_2][x_2]=union[temp[y_2][x_2]-1
    temp = [[0] * N for i in range(N)]
    visited = [[0] * N for i in range(N)]
    res+=1

print(res)

saojin10 5년 전 1

코드를 자세히 읽어보지는 않았는데 일단 눈에 띄는 부분이 있어서 알려드리자면

파이썬은 원래가 느린 언어기 때문에 자료구조 선정에 신경을 좀 쓰셔야 합니다.

queue라고 선언하신 변수는 사실 큐가 아니라 리스트죠? list에서 pop(0)를 하면 n시간이 걸립니다.

BFS에서 확인하는 모든 경로에 대해 n시간을 소모하는건 별로 좋아보이지 않네요.

사실 대부분의 경우에 큐 대신에 리스트를 사용하면 시간초과가 납니다.

collections의 deque를 사용해보시는걸 추천드립니다.

백준 블로그의 관련 글도 있습니다. Python 항목을 한번 읽어보세요~

https://www.acmicpc.net/blog/view/70

q0115643 5년 전 1

Queue에 넣으면서 visited를 바로 True로 바꿔주지 않으면 같은 위치가 중복적으로 Queue에 들어갑니다.

cmg7111 5년 전 0

두분 모두 감사드립니다. 방문 체크 순서 문제도 있었군요! 해당 글 읽어보고 수정 해보겠습니다.

cmg7111 5년 전 0

추가로 deque 부분은 처음 알았네요 ㅜㅜ 감사합니다.

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

문제

문제

출처

ICPC

인구이동 파이썬 시간초과 질문 드립니다

cmg7111 5년 전 0

saojin10 5년 전 1

q0115643 5년 전 1

cmg7111 5년 전 0

cmg7111 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말