글 읽기 - 이 문제 파이썬으로 시간초과 안나는 방법좀 있을까요?

dhdbsgn111 5년 전 0

완전탐색하는데 시간이 너무너무 오래걸립니다...

import sys
ma=[]
if __name__=="__main__" :
	n,m=map(int,sys.stdin.readline().split())
	for i in range(n):
		ma.append(list(map(int,sys.stdin.readline().split())))
		
l=[]
for x in range(n):
	for y in range(m):
		l.append([(x,y),ma[x][y]])

virus=[]
empty=[]
for i in range(len(l)):
	if l[i][1]==2:
		virus.append(l[i][0])
for i in range(len(l)):
	if l[i][1]==0:
		empty.append(l[i][0])

dx=[0,0,1,-1]
dy=[1,-1,0,0]
		
def bfs(ma,start,k,m):
	c=[]
	q=[start]
	while q:
		n=q.pop(0)
		if n not in c:
			c.append(n)
			for i in range(len(dx)):
				dxx=n[0]+dx[i]
				dyy=n[1]+dy[i]
				if dxx>=0 and dxx<k and dyy>=0 and dyy<m and ma[dxx][dyy]==0:
					if (dxx,dyy) not in c:
						q.append((dxx,dyy))
	return c
	
	

em=len(empty)

c = [False]*(em)
a = [0]*3
l2=[]
def go(index, start, n, m,l2):
    if index == m:
        l2.append(a[:])
        return
    for i in range(start, n+1):
        if c[i]:
            continue
        c[i] = True
        a[index] = i
        go(index+1, i+1, n, m,l2)
        c[i] = False

go(0,0,em-1,3,l2)

ans=[]

for i in range(len(l2)):
	for j in range(3):
		e1=empty[l2[i][j]]
		ma[e1[0]][e1[1]]=1
	con=[]
	for k in range(len(virus)):
		c1=bfs(ma,virus[k],n,m)
		con+=c1
	con=list(set(con))	
	ans.append(len(con))
	
	for p in range(3):
		e1=empty[l2[i][p]]
		ma[e1[0]][e1[1]]=0

f1=0
for x in range(n):
	for y in range(m):
		if ma[x][y]==1:
			f1+=1
f=n*m
f2=min(ans)
print(f-f1-f2-3)

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

문제

문제

출처

ICPC

이 문제 파이썬으로 시간초과 안나는 방법좀 있을까요?

dhdbsgn111 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말