글 읽기 - 파이썬 시간 관련 질문 드립니다.

sigk218 3년 전 0

아래 코드를 로컬에서 돌리면, 8초 정도의 시간이 걸립니다.

문제 제한 시간은 2초인데 어떻게 정답으로 통과하는 것인지 궁금합니다. ㅜㅜ

import time
start_time = time.time()
n, m = map(int, input().split())
mymap = []

candidates = []

for i in range(n):
    line = list(map(int, input().split()))
    mymap.append(line)
    for j in range(m):
        if line[j] == 0:
            candidates.append((i, j))


import itertools, collections
answer = 0
for pick in list(itertools.combinations(candidates, 3)):
    # 벽을 세운다
    for i, j in pick:
        mymap[i][j] = 1
    # 퍼뜨린다
    change = []
    visited = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            # 시작점
            if visited[i][j]: continue
            if mymap[i][j] == 2:
                visited[i][j] = 1
                q = collections.deque([(i, j)])
                while q:
                    x, y = q.popleft()
                    for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):
                        nx = x + dx
                        ny = y + dy
                        if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
                        if visited[nx][ny] or mymap[nx][ny]: continue
                        q.append((nx, ny))
                        mymap[nx][ny] = 2
                        change.append((nx, ny))
                        visited[nx][ny] = 1

    count = 0
    # 갯수를 센다
    for i in range(n):
        for j in range(m):
            if mymap[i][j] == 0:
                count += 1
    answer = max(count, answer)

    # 복원 한다
    for i, j in change:
        mymap[i][j] = 0

    for i, j in pick:
        mymap[i][j] = 0

print(answer)
print('time: ', time.time()-start_time)

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

문제

문제

출처

ICPC

파이썬 시간 관련 질문 드립니다.

sigk218 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말