글 읽기 - [파이썬]시간초과 한번만 도와주세욥..ㅠㅠ

jj1218 4년 전 0

안녕하세요. 고수님들

채점중 3%에서 멈춘 후 시간초과로 결과 출력이 됩니다.

침수가 안됐을 때에 대한 반례가 많은데 다 처리했다고 생각하거든요.ㅠㅠ

한번만 도와주십요. 부탁드립니다.

감사합니다.

N = int(input())
map = [[0] * N for _ in range(N)]
map_copy = map
max = 0
safe = 0

for row in range(N):
    line = input().split()
    for index in range(N):
        map[row][index] = int(line[index])
        if int(line[index]) > max:
            max = int(line[index])

def BFS(row, index):
    q = []
    q.append((row, index))
    roads = [(1,0), (0,1), (-1,0), (0,-1)]
    while q:
        x, y = q.pop(0)
        visited[x][y] = True
        for next_x, next_y in roads:
            next_x, next_y = x + next_x, y + next_y
            if next_x < 0 or next_y < 0 or next_x >= N or next_y >= N:
                continue
            if map_copy[next_x][next_y] != 0 and not visited[next_x][next_y]:
                q.append((next_x, next_y))

def FLOOD(height): #홍수 map만들기
    for row in range(N):
        for index in range(N):
            if map_copy[row][index] <= height:
                map_copy[row][index] = 0

for height in range(max + 1): #침수값 0 ~ 최대값까지
    visited = [[False] * N for _ in range(N)] # visited 초기화
    map_copy = map  # map 초기화
    tmp = 0 #안전지역

    FLOOD(height)

    for row in range(N):
        for index in range(N):
            if map_copy[row][index] != 0 and not visited[row][index]:
                BFS(row, index)
                tmp += 1
    if tmp > safe:#safe존보다 많으면 교체
        safe = tmp

print(safe)

djm03178 4년 전 3

시간 초과는 프로그램이 제한 시간을 넘길 때까지 종료가 안 됐기 때문에 나온 것이므로 답이 맞는지 여부와는 관계가 없습니다.

1. Python3는 너무 느립니다. PyPy3를 사용해 보세요.

2. input도 너무 느립니다. https://www.acmicpc.net/proble... 를 참고해서 빠르게 바꿔보세요.

3. BFS는 큐에서 뺀 다음이 아니라 큐에 넣을 떄 방문 표시를 해야 시간 복잡도가 망가지지 않습니다.

4. list.pop(0)는 처음 원소를 지운 후 뒤의 원소를 전부 한 칸씩 앞으로 당겨오기 때문에 리스트의 길이에 비례하는 시간이 걸립니다. collections.deque를 사용하세요. 그리고 https://www.acmicpc.net/proble... 를 먼저 풀어보시기를 권장합니다.

djm03178 4년 전 1

다시 보니 아까 올리신 11724번 질문이 아니군요. 1번 2번이 이 문제에는 그다지 해당되지 않겠지만 알아두시면 좋습니다.

jj1218 4년 전 0

djm03178

감사합니당. 참고해서 수정해보곘습니당!!!

jj1218 4년 전 0

djm03178

정말 너무너무너무 감사합니다ㅠㅠ

3. BFS는 큐에서 뺀 다음이 아니라 큐에 넣을 떄 방문 표시를 해야 시간 복잡도가 망가지지 않습니다.

==> 이것도 같이 수정했습니다. 감사합니다!!! 제가 너무 수박 겉핥기 식으로 공부한거 같습니다.

==> list가 편해서 사용했는데 deque로 바꿨더니 바로 처리가 됐습니다.

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

문제

문제

출처

ICPC

[파이썬]시간초과 한번만 도와주세욥..ㅠㅠ

jj1218 4년 전 0

djm03178 4년 전 3

djm03178 4년 전 1

jj1218 4년 전 0

djm03178

감사합니당. 참고해서 수정해보곘습니당!!!

jj1218 4년 전 0

djm03178

정말 너무너무너무 감사합니다ㅠㅠ

==> 이것도 같이 수정했습니다. 감사합니다!!! 제가 너무 수박 겉핥기 식으로 공부한거 같습니다.

==> list가 편해서 사용했는데 deque로 바꿨더니 바로 처리가 됐습니다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말