글 읽기 - 파이썬 시간초과

boompatron 2년 전 0

파이썬으로 풀고 있는데 계속 시간 초과가 납니다.... 접근 방식이 잘못된 걸까요??

제 풀이 방식은 우선 각 대륙 별로 테두리에 해당하는 좌표들을 coord라는 이차원 리스트에 넣은 다음 다른 대륙의 두 개의 점의 좌표를 이용해 두 좌표 사이의 거리를 계산을 해서 최솟값을 산출하는 방식인데...

시간을 줄일 수 있는 방식이 있는지, 아니면 접근이 완전을 완전히 잘못해서 다시 해야 하는지 잘 모르겠습니다...

import sys
from collections import deque
dxs, dys = [1, -1, 0, 0], [0, 0, 1, -1]
N = int(sys.stdin.readline().rstrip())
g = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]
visited = [[False for _ in range(N)] for __ in range(N)]
num_of_continent = 0
coord = [[]]


def inRange(x, y):
    return 0 <= x < N and 0 <= y < N


def BFS(x, y, append_pos):
    dq = deque()
    dq.appendleft([x, y])
    visited[y][x] = True
    while dq:
        tmp_x, tmp_y = dq.pop()
        for dx, dy in zip(dxs, dys):
            nx, ny = tmp_x + dx, tmp_y + dy
            #이 if 문은 대륙을 정의하기 위해 만든 조건문입니다
            if inRange(nx, ny) and g[ny][nx] and not visited[ny][nx]:
                dq.appendleft([nx, ny])
                visited[ny][nx] = True
            #이 if 문은 대륙의 테두리 부분을 coord에 추가하기 위해 넣은 조건문입니다
            if inRange(nx, ny) and g[ny][nx] == 0 and [tmp_x, tmp_y] not in coord[append_pos]:
                coord[append_pos].append([tmp_x, tmp_y])


for i in range(N):
    for j in range(N):
        if g[i][j] and not visited[i][j]:
            #대륙의 수를 늘려가면서 BFS를 수행합니다
            BFS(j, i, num_of_continent)
            num_of_continent += 1
            coord.append([])
                
# for i in range(len(coord) - 1):
#     print(len(coord[i]), end=":")
#     for j in range(len(coord[i])):
#         print(coord[i][j], end=" ")
#     print()
                
ans = 123456789
for i in range(len(coord) - 1):
    for j in range(len(coord[i])):
        for k in range(len(coord) - 1):
            for l in range(len(coord[k])):
                if i != k:
                    # i랑 k가 같으면 같은 대륙내에 있는 것이므로 달라야 합니다
                    xdiff = abs(coord[i][j][0] - coord[k][l][0])
                    ydiff = abs(coord[i][j][1] - coord[k][l][1])
                    tmp = 0
                    if xdiff == 0:
                        tmp = ydiff - 1
                    elif ydiff == 0:
                        tmp = xdiff - 1
                    else:
                        tmp = xdiff + ydiff - 1
                    if tmp < ans:
                        ans = tmp
print(ans)
# 예제 출력 결과
# 위의 주석친 부분을 주석 해제하고 출력하면 밑에처럼 나옵니다
# 각 대륙의 테두리에 해당하는 부분의 좌표
# 9:[2, 0] [1, 1] [0, 2] [3, 1] [2, 2] [3, 2] [2, 3] [4, 3] [3, 4] 
# 6:[7, 0] [8, 1] [8, 2] [9, 3] [9, 4] [9, 5] 
# 5:[4, 7] [5, 7] [4, 8] [5, 8] [6, 8] 
# 정답
# 3

sinsung6722 2년 전 1

제가 볼때는 알고리즘상의 시간 복잡도는 만족하나, 구현 과정에서 특정 라이브러리를 잘못 사용해서 문제가 된 것 같습니다.

소스코드 28번째 줄을 보면,

'[tmp_x, tmp_y] not in coord[append_pos]:'

즉, 특정 좌표가 경계값 목록에 이미 포함되었는지 확인하는 소스코드가 있습니다.

리스트에서 in 연산자를 통해서 찾기 때문에 검색에 걸리는 시간복잡도는 리스트의 데이터 개수에 비례한 O(n) 입니다.

그리고, 이 부분을 이용해서 시간초과를 일으키는 저격 데이터를 만들 수 있습니다.

100

1 1 1 1 1 ...

1 0 1 0 1 ...

1 1 1 1 1 ...

0 1 0 1 0 ...

1 1 1 1 1 ...

...

과 같이 데이터를 생성시킬 경우, coord[append_pos]에 담기는 경계좌표는 0과 인접한 1의 개수에 비례하므로, 약 7500개가 리스트에 담기게 됩니다.

또한, in을 이용한 리스트 비교는 1이 담겨진 큐에 대해서 4방향으로 검색하므로, 약 7500*4 = 30000 번의 비교연산이 수행됩니다.

이를 곱하면 7500 * 30000 = 225000000(2억 2500만)이 되어서, 시간초과제한인 2초를 넘기기에 충분하게 됩니다.

coord에 담기는 값을 리스트가 아닌, set()으로 변경시켜보시길 바랍니다.

리스트가 아닌, set()을 쓰면 존재여부를 확인하는데에 해시 계산시간인 c가 걸리므로, 검색을 O(1) 안에 해결할 수 있습니다.

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

문제

문제

출처

ICPC

파이썬 시간초과

boompatron 2년 전 0

sinsung6722 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말