글 읽기 - (파이썬)연구소3 두 코드의 차이를 모르겠습니다.

ebbunnim 3년 전 0

저는 두 코드가 똑같다고 생각하는데, 왜 아래 것은 시간초과가 나는 걸까요??

정말 궁금합니다 ㅠㅠ

# 맞은 코드
from collections import deque

if __name__ == '__main__':
    N,M = map(int, input().split())
    arr=[list(map(int, input().split())) for _ in range(N)]
    virus = []
    V = 0
    K=0
    for i in range(N):
        for j in range(N):
            if arr[i][j]==2:
                virus.append((i,j))
                V+=1
            elif arr[i][j]==0:
                K += 1
    ans =10**9

    def bfs(distance,res):
        global ans

        Q = deque()
        for r in res:
            Q.append(r)
            distance[r[0]][r[1]]=0
        t=infected=0

        while Q :
            idxs = Q.popleft()
            for dr, dc in (-1,0),(1,0),(0,1),(0,-1):
                nr = idxs[0] + dr
                nc = idxs[1] + dc
                if 0<=nr<N and 0<=nc<N and distance[nr][nc]==-1 and arr[nr][nc]!=1:
                    distance[nr][nc]=distance[idxs[0]][idxs[1]]+1
                    Q.append((nr, nc))
                    if arr[nr][nc]==0:
                        infected+=1
                        t = distance[nr][nc]

        # 다 퍼뜨린 후에는
        if K == infected:
            ans = min(ans, t)


    select = [False]*10

    def dfs(idx, cnt, V):
        if cnt == M:
            distance = [[-1] * N for _ in range(N)]
            res=[]
            for i in range(V):
                if select[i]:
                    res.append((virus[i][0],virus[i][1]))
            bfs(distance,res)
            return

        for i in range(idx, V):
            if not select[i]:
                select[i] = True
                dfs(i + 1, cnt + 1, V)
                select[i] = False

    dfs(0, 0, V)

    if ans == 10**9:
        print(-1)
    else:
        print(ans)
        
        
        
 # 시간초과 코드
import sys
sys.stdin = open('input.txt','r')

from collections import deque

if __name__ == '__main__':
    N,M = map(int, input().split())
    arr=[list(map(int, input().split())) for _ in range(N)]
    virus = []
    V = 0
    K = 0
    selected = [False]*10
    Q = deque()

    for i in range(N):
        for j in range(N):
            if arr[i][j]==2:
                virus.append((i,j))
                V+=1
            elif arr[i][j]==0:
                K += 1
    ans =10**9

    def bfs(distance):
        global ans

        infected=0
        t=0

        while Q :
            r,c = Q.popleft()
            for dr, dc in (-1,0),(1,0),(0,1),(0,-1):
                nr = r + dr
                nc = c + dc
                if 0<=nr<N and 0<=nc<N and distance[nr][nc]==-1 and arr[nr][nc]!=1:
                    distance[nr][nc]=distance[r][c]+1
                    Q.append((nr, nc))
                    if arr[nr][nc]==0:
                        infected+=1
                        t = distance[nr][nc]

        # 다 퍼뜨린 후에는
        if K == infected:
            ans = min(ans, t)


    def dfs(sidx,cnt,V): # select activate virus
        if cnt==M:
            # bfs
            distance = [[-1] * N for _ in range(N)]
            for i in range(V):
                if selected[i]:
                    Q.append((virus[i][0],virus[i][1]))
                    distance[virus[i][0]][virus[i][1]]=0
            bfs(distance)
            return
        for i in range(sidx,V):
            if not selected[i]:
                selected[i]=True
                dfs(sidx+1,cnt+1, V)
                selected[i]=False

    dfs(0,0,V) #M이 아니라 V
    if ans == 10**9:
        print(-1)
    else:
        print(ans)

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

문제

문제

출처

ICPC

(파이썬)연구소3 두 코드의 차이를 모르겠습니다.

ebbunnim 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말