[BOJ] 17142

문제

me

import sys
from collections import deque
from copy import deepcopy
from itertools import combinations
input = sys.stdin.readline

n,m = map(int,input().split())
spaces=[list(map(int,input().split())) for _ in range(n)]
viruses=[]
has_blank=False
for i in range(n):
    for j in range(n):
        if spaces[i][j]==2:
            viruses.append([i,j])
        elif spaces[i][j]==0: has_blank=True
if not has_blank:
    print(0)
    sys.exit()
def spread(activated,spaces):
    dx=[-1,0,+1,0]
    dy=[0,-1,0,+1]
    q=[]
    visited=[[False]*n for _ in range(n)]
    for x,y in activated:
        q.append([0,x,y])
        spaces[x][y]=-2
        visited[x][y]=True
    q = deque([[0,x,y] for x,y in activated])
    while q:
        time,x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i];
            ny = y + dy[i];
            if not (-1 < nx < n and -1 < ny < n) or visited[nx][ny]: continue
            visited[nx][ny]=True # 방문으로 바꾸기
            if spaces[nx][ny] ==0 :
                # 벽만 아니면 모두 복제
                spaces[nx][ny] = time+1 # 바이러스로 복제 (시간으로 바꿔두기)
                q.append([time+1, nx, ny])
            elif spaces[nx][ny]==2:
                spaces[nx][ny]=-3
                q.append([time+1,nx,ny])
            else:
                spaces[nx][ny]=-1
    time=0
    for space in spaces:
        if space.count(0)!=0:
            return -1
        time = max(time,max(space))
    return time

def choose():
    global min_time
    for activated in combinations(viruses,m):
        time = spread(activated,deepcopy(spaces))
        if time != -1:
            # -1이면 모든 빈칸에 퍼뜨리지 못한 상태
            min_time=min(min_time,time)

min_time=int(1e9)
choose()
if min_time==int(1e9):
    print(-1)
else:
    print(min_time)

1. choose를 재귀로 했었다. 시간초과가 난다. > itertools의 combinations를 이용해야한다.

   조합 코드

2. visit과 시간을 동시에 저장하는 방법이 있다.

others

출처

def bfs(virus_list):
    dist = [[-1] * N for _ in range(N)]
    dq=deque()
    for pos in virus_list:
        dq.append(pos)
        dist[pos[0]][pos[1]] = 0
    max_dist=0
    while dq:
        x,y=dq.popleft()
        for k in range(4):
            nx=x+di[k][0]
            ny=y+di[k][1]

            if 0<=nx<N and 0<=ny<N and map_data[nx][ny]!=1 and dist[nx][ny]==-1:
                dist[nx][ny]=dist[x][y]+1
                if map_data[nx][ny]==0:
                    max_dist=max(max_dist,dist[nx][ny])
                dq.append([nx,ny])

    a = list(sum(dist,[]))
    if a.count(-1)==list(sum(map_data,[])).count(1):	# 방문 안 한 곳이 벽의 개수와 동일한지
        ans.append(max_dist)	# 리스트없이 바로 min값 구해도 됨

1. dist라는 2차원 배열을 모두 -1로 둔다.
2. 해당 위치가 벽이 아니고 -1일때만 +1을 해준다.
3. 현재 dist, 내꺼에서만 따지면 time은 빈 칸일때만 업데이트 시켜준다.
4. 방문 안한 곳(dist)과 벽의 개수(map)가 동일한지만 따지면 빈칸 확인 가능하다

난 활용되는 배열도 너무 많았다. 좀 더 간단하게 할 수 있었다..!!!