글 읽기 - 시간초과가 나는 이유가뭘까요?

hskim9337 1년 전 0

얼핏 생각해봐도 문제에서 최대값이 8x8 이니까

모든 경우의 수를 다 검사해도

64C3 이니까 총 경우의수가 5만개도 안되는데 이 경우에서 시간초과가 날 수가 있나요?

import sys
input = sys.stdin.readline

n,m = map(int,input().split())

graph = [list(map(int,input().split())) for _ in range(n)]
temp = [[0]*m for _ in range(n)]

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

result = 0

def get_score():
    score=0
    for i in range(n):
        for j in range(m):
            if temp[i][j]==0:
                score +=1
    return score

def virus(x,y):
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]

        if nx>=0 and nx<n and ny>=0 and ny<m:
            if temp[nx][ny]==0:
                temp[nx][ny]=2
                virus(nx,ny)
def dfs(count):
    global result
    if count == 3:
        for i in range(n):
            for j in range(m):  
                temp[i][j] = graph[i][j]
        for i in range(n):
            for j in range(m):
                if temp[i][j]==2:
                    virus(i,j)
        result = max(result,get_score())
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j]==0:
                graph[i][j]=1
                count +=1
                dfs(count)
                graph[i][j]=0
                count -=1
dfs(0)
print(result)

choko100 1년 전 2

안녕하세요, dfs() 함수 안에서 n x m 탐색을 3번 한 후에, virus의 시작점을 찾기 위해 n x m 탐색을 1번 더 하고, 그 안에서 virus() 함수를 진입하면 재귀로 거의 n x m 정도가 또 호출되지 않을까 싶습니다.

(1) dfs 함수에서 count 가 0에서 3이 될 때까지 이중 포문 3번

def dfs(count):

for i in range(n): // 44 번 라인

for j in range(m):

64 x 64 x 64 = 262,144

(2) dfs 함수에서 virus() 를 호출할 때 이중 포문 추가

def dfs(count):

if count == 3:

for i in range(n): // 37 번 라인

for j in range(m):

262,144 x 64 = 16,777,216

(3) virus 함수에서 0 인 곳을 모두 2 로 만들 때까지 재귀 진행

16,777,216 x 64 = 1,073,741,824

hskim9337 1년 전 0

감사합니다 이해했습니다.

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

문제

문제

출처

ICPC

시간초과가 나는 이유가뭘까요?

hskim9337 1년 전 0

choko100 1년 전 2

hskim9337 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말