글 읽기 - Python 시간초과 질문드립니다..

celestial 2년 전 0

원래 C++ 사용자라 익숙하지는 않은데요

계속 시간초과가 납니다.

visited=[]를 전역 선언해주어 방문했던 곳을 재방문하지 않도록 해주었고

한번 탐색을 돌 때마다(늑대를 발견하는 좌표에서) BFS를 시작, 늑대와 양의 개수를 구한 뒤 조건에 맞게 처리하였습니다.

그런데 계속 시간 초과가 뜨네요.

음 한번 방문했던 곳을 재방문하지도 않고, 뭔가 C++에서 accept 되었던 코드를 그대로 군더더기 없이 conversion 한 듯 보이는데(?) 왜 이런 결과가 나오는지 궁금합니다.

도와주시면 대단히 감사합니다.

R,C = map(int,input().split())

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


mapp = [[0]*C for _ in range(R)]


def BFS(queue,cnt,visited):
    #print('currentx :',curx,'currenty :',cury)
    while queue:
        curx,cury = queue[0][0],queue[0][1]
        del queue[0] 
        
        for i in range(4):
            nextx,nexty = curx+dx[i],cury+dy[i]
            #print('다음 x :',nextx,'다음 y :',nexty)
            if nextx>=0 and nextx<R and nexty>=0 and nexty<C and mapp[nextx][nexty]!='#' and (nextx,nexty) not in visited:
                # . 이든 o이든 v이든 일단 카운트할 수 있으니까.
                #print("<<<탐색 시작>>>")


                if mapp[nextx][nexty]=='v':
                    #print(nextx,nexty,'에서 늑대 발견')
                    cnt[0]+=1
                    visited.append((nextx,nexty))
                    queue.append((nextx,nexty))
                    #print("queue :", queue[0][0],queue[0][1])

                elif mapp[nextx][nexty]=='o':
                    #print(nextx,nexty, '에서 양 발견')
                    visited.append((nextx,nexty))
                    queue.append((nextx,nexty))
                    cnt[1]+=1
                    #print("queue :",queue[0][0],queue[0][1])
                
                else:
                    
                    #print(nextx,nexty,'에서 길 발견')
                    visited.append((nextx,nexty))
                    queue.append((nextx,nexty))
                    #print("queue :",queue[0][0],queue[0][1])
                    
                       
    # queue를 전부 돌고 난 다음 양과 늑대의 개수 결정
    # cnt[0] : 늑대 cur[1] : 양
    if cnt[0] >= cnt[1]:
        #양을 전부 다 먹음.
        cnt[1]=0
    else:
        cnt[0]=0 

    return cnt[0],cnt[1]



for i in range(R):
    cur = input()

    for ii in range(len(cur)):
        mapp[i][ii]=cur[ii]



wolvesres,sheepres=0,0

### 전체 방문을
visited=[]

for r in range(R):
    for c in range(C):
        
        if mapp[r][c]=='v' and (r,c) not in visited:
            
            #print(r,c,"늑대 start")
            cnt=[0,0]
            cnt[0]+=1
            queue=[]
            visited.append((r,c))
            queue.append((r,c))
            
            w,s=BFS(queue,cnt,visited)
            wolvesres+=w 
            sheepres+=s


print(sheepres,wolvesres)

ahj1592 2년 전 0

혹시 해결하셨나요?

`visited`가 리스트라서 (x, y) not in visited'가 선형시간이라서 느립니다. 이 부분을 O(1)로 하시면 됩니다.

예를들어 visited를 딕셔너리로 바꾸시거나, visited를 2차원배열로 만들어서 True, False로 확인하는 방법이 있습니다.

celestial 2년 전 0

@ahj1592 님, 댓글 달아주셔서 감사합니다!

네네 c++에서 하던 대로 visited를 2차원 배열로 만들어서 O(1)로 접근하도록 했더니 accepted 되었었습니다ㅎㅎ

앞으로 계속 python으로 관련 문제를 풀 때 visited도 2차원으로 선언해서 풀고 있습니다.

감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

Python 시간초과 질문드립니다..

celestial 2년 전 0

ahj1592 2년 전 0

celestial 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말