글 읽기 - 20%에서 시간초과가 나오는데 뭐가 문제일까요..?

mimmyum 6년 전 0

어느 부분에서 시간초과가 나는지를 모르겠네요... 문제 답은 제대로 나오는거같은데...

def BFS(mapList, visited, i, j) :
    queue = []
    queue.append([i,j])
    dx = [-1,-1,-1,0,0,1,1,1]
    dy = [-1,0,1,-1,1,-1,0,1]
    while queue :
        now = queue.pop(0)
        row = now[0]
        col = now[1]
        visited[row][col] = 1

        for i in range(8) :
            if mapList[row+dx[i]][col+dy[i]] =='1' :
                if visited[row+dx[i]][col+dy[i]] != 1 :
                    queue.append([row+dx[i],col+dy[i]])


if __name__ == "__main__" :
    w, h = [int(x) for x in input().split()]
    while w != 0 :
        total = 0
        mapList = ['0']*(h+2)
        mapList[0] = ['0']*(w+2)
        mapList[h+1] = ['0'] * (w+2)
        visited = [0]*(h+2)
        for i in range(h+2) :
            visited[i] = [0]*(w+2)
        for i in range(1,h+1) :
            oneLine = ['0']*(w+2)
            inputLine = list(input().split())
            oneLine[1:w+1] = inputLine
            mapList[i] = oneLine

        for i in range(1,h+1) :
            for j in range(1,w+1) :
                '''
                if visited[i][j] == 1 :
                    continue
                else :
                    """
                    if mapList[i][j] == '0' :
                        visited[i][j] = 1
                        continue
                    else :
                    """
                    if mapList[i][j] == '1':
                        total+= 1
                        BFS(mapList, visited,i, j)
                '''
                if mapList[i][j] == '1' :
                    if visited[i][j] == 1 :
                        continue
                    else :
                        total+=1 
                        BFS(mapList, visited, i , j)
        print(total)
        w, h = [int(x) for x in input().split()]

ntopia 6년 전 0

제가 한가지 원인을 추측해보았는데요,

python 의 평범한 list 라면

맨 앞의 원소를 pop(0) 로 지우는 것은

list의 원소개수만큼의 시간이 걸릴 것 같습니다.

https://stackoverflow.com/ques...

여기에 그런 얘기도 있고요

그래서 시간초과가 나는 것이 아닐까요?

queue 가 제대로 구현된 것을 사용해야할 듯 싶습니다.

ntopia 6년 전 0

파이썬에 deque 이 따로 있대요.

이건 맨 앞에서 뽑는 연산의 시간복잡도가 O(1) 임이 보장되어있습니다.

mimmyum 6년 전 0

와.. 그런 내용은 몰랐는데.. 이번에 새롭게 알게되었네요...

감사합니다!!

일단 deque로 바꾸고 다른 내용 살펴봤는데, 보니깐 queue에서 중복되어 같은 섬을 확인하는 경우가 있어서

시간 초과가 나왔던것 같네요. 그 부분 고치니깐 통과했습니다.

ntopia님, 같이 고민해주셔서 감사합니다!!!

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

문제

문제

출처

ICPC

20%에서 시간초과가 나오는데 뭐가 문제일까요..?

mimmyum 6년 전 0

ntopia 6년 전 0

ntopia 6년 전 0

mimmyum 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말