문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.  일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

풀이

시간제한과 입력 크기가 매우 널널했다. (파이썬은 시간을 더 줬을 것 같긴한데) 시간제한 2초에, 인풋크기는 3<=N , M<= 8 이다. 즉 브루트포스 로 풀기에 충분하다는 생각이 들었다 !

코드

데이터 입력 부분

class LAB:
    def read(self):
        [self.n,self.m]=list(map(int,input().split()))
        self.box=[]
        self.one=0
        for _ in range(self.n):
            put=list(map(int,input().split()))
            self.one+=put.count(1)
            self.box.append(put)
        self.dx=[-1,0,1,0]
 		  self.dy=[0,1,0,-1]
        self.checked=[[False for _ in range(self.m)] for k in range(self.n)]

벽을 칠 수 있는 (wall1,wall2,wall3) 각 case 구해주기

71156AF7-E275-4389-9A46-AC20FA72BE9E 여기에서 노란색으로 형광펜 친 0 부분 (빈 칸)에는 모두 벽을 세울 수 있다. 벽은 총 3개 세워야하므로 전체 0 개수 중에 순서에 상관 없이 3개를 고르는 조합 (wall1,wall2,wall3) 페어를 다 구해주어야한다. 이 부분은 파이썬 라이브러리를 썼다. ‘2’ (; 바이러스가 있는 현재 위치)에서부터 바이러스가 타고타고 퍼지므로 후에 bfs 부분에 필요할 것을 대비해서 2 가 어디 자리에 있는지도 미리 second_ind 에 넣어주었다.

def candidate(self):
        self.zero_ind=[]
        self.second_ind=[]
        for i in range(self.n):
            for j in range(self.m):
                if self.box[i][j]==0:
                    self.zero_ind.append((i,j))
                elif self.box[i][j]==2:
                    self.second_ind.append((i,j))
        self.cand=list(combinations(self.zero_ind,3))

BFS 하기 1) cand 에 세 벽을 어떻게 칠지 각 경우의 수 별 case (wall1,wall2,wall3) 가 담겨져있다. 각 case 별 안전지대 수를 다 구해주어야한다. (브루트포스 방식이므로 각각 안전지대 수를 구해주고 후에 비교한 후 최대만 남긴다). 이 때 각 case 별로 원래 있던 연구소에 벽을 칠 위치가 다르므로, 시험을 위해 각 case 에서 사용할 임시 연구소를 deepcopy 한다.

def solve(self):
        ans=float("inf")            
        for item in self.cand:
            s=0
            checked=[]
            tmp=copy.deepcopy(self.box)
            confirmed=deque()
            for x in range(3):
                c=item[x]
                c_i,c_j=c
                tmp[c_i][c_j]=1

2) 안전지대를 세기 위해서는 바이러스가 있는 2 부터 시작하여 실제 시험을 진행하면 된다. (시험; bfs 방식으로 진행) ED5DB134-CFF5-46E9-BF78-D6DC0150988F 먼저 2 노드의 위치를 confirmed 에 넣어주고 check 했다고 표시해준다. (False -> True)

for ind in self.second_ind:
                confirmed.append(ind)
                self.checked[ind[0]][ind[1]]=True

그다음부터 전형적인 BFS 이다.

while confirmed:
                coor=confirmed.popleft()
                for i in range(4):
                    newi=coor[0]+self.dx[i]
                    newj=coor[1]+self.dy[i]
                    if not (0<=newi<self.n and 0<=newj<self.m):
                        continue
                    if self.checked[newi][newj]:
                        continue
                    if tmp[newi][newj]==1:
                        continue
                    if tmp[newi][newj]==0:
                        tmp[newi][newj]=2
                        self.checked[newi][newj]==True
                        confirmed.append((newi,newj))

Bfs 가 끝났으면 바이러스가 퍼질 수 있는 부분은 다 0 에서 2로 바뀌었을 것이다. 0 으로 남아있는 안전지대를 세어준다.

for i in range(self.n):
                for j in range(self.m):
                    if tmp[i][j]==0:
                        s+=1

다른 case에서 세어준 안전지대 수를 뛰어넘었다면 기록을 갱신해준다. (나 갱신이라는 단어를 엄청 많이 사용하는 것 같다 왜인지는 모름 ㅋㅋ)

if s>ans:
                ans=s

전체 코드 (통과된 버전)

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

class LAB:
    def read(self):
        [self.n,self.m]=list(map(int,input().split()))
        self.box=[]
        self.one=0
        for _ in range(self.n):
            put=list(map(int,input().split()))
            self.box.append(put)
        self.dx=[-1,0,1,0]
        self.dy=[0,1,0,-1]
        self.checked=[[False for _ in range(self.m)] for k in range(self.n)]
    def candidate(self):
        self.zero_ind=[]
        self.second_ind=[]
        for i in range(self.n):
            for j in range(self.m):
                if self.box[i][j]==0:
                    self.zero_ind.append((i,j))
                elif self.box[i][j]==2:
                    self.second_ind.append((i,j))
        self.cand=list(combinations(self.zero_ind,3))
    
    def solve(self):
        ans=float("-inf")            
        for item in self.cand:
            s=0
            tmp=copy.deepcopy(self.box)
            confirmed=deque()
            for x in range(3):
                c=item[x]
                c_i,c_j=c
                tmp[c_i][c_j]=1
            for ind in self.second_ind:
                confirmed.append(ind)
                self.checked[ind[0]][ind[1]]=True
            while confirmed:
                coor=confirmed.popleft()
                for i in range(4):
                    newi=coor[0]+self.dx[i]
                    newj=coor[1]+self.dy[i]
                    if not (0<=newi<self.n and 0<=newj<self.m):
                        continue
                    if self.checked[newi][newj]:
                        continue
                    if tmp[newi][newj]==1:
                        continue
                    if tmp[newi][newj]==0:
                        tmp[newi][newj]=2
                        self.checked[newi][newj]==True
                        confirmed.append((newi,newj))
            for i in range(self.n):
                for j in range(self.m):
                    if tmp[i][j]==0:
                        s+=1   
         
            if s>ans:
                ans=s
        print(ans)        

lb=LAB()
lb.read()
lb.candidate()

처음 코드 시간초과한 부분

1) 처음에는 check 한 노드의 인덱스를 checked 에 담아주고, if ~ in checked 이런 식으로 코드를 짰다. 그 결과 일일이 checked 에 있는 n 개의 노드 좌표를 다 돌면서 이미 방문한 노드인지를 검사하기 때문에 시간복잡도가 O(n) 이 되어서 시간초과되었다. 그냥 모든 노드 개수대로 [False * m] * n 인 checked 리스트를 만들어주고, 방문할 때마다 True 로만 바꾸어주고 if checked[~][~]: 이런 식으로 True 인지만 검사해주면 시간복잡도가 O(1)밖에 되지 않는다는 것을 깨달았다. 😳 어메이징 ~!

2) 이건 시간초과 관련된 부분은 아닌데 이웃노드들을 구해주는 코드를 짤 때 미리 dx, dy 에 각 좌표가 이동할 수 있는 경우의 수를 미리 넣어주고 for 문을 돌리는게 훨씬 깔끔하다는 것을 알게 되었다. 원래 코드는 이런 식으로 작성해서 훨씬 지저분했다.

s_i,s_j=coor
                if s_i-1>=0:
                    if [s_i-1,s_j] not in checked:
                        if tmp[s_i-1][s_j]==0:
                            confirmed+=[[s_i-1,s_j]]
                            checked.append([s_i-1,s_j])
                if s_j-1>=0:
                    if [s_i,s_j-1] not in checked:
                        if tmp[s_i][s_j-1]==0:
                            confirmed+=[[s_i,s_j-1]]
                            checked.append([s_i,s_j-1])
                if s_i+1<=self.n-1:
                    if [s_i+1,s_j] not in checked:
                        if tmp[s_i+1][s_j]==0:
                            confirmed+=[[s_i+1,s_j]]
                            checked.append([s_i+1,s_j])
                if s_j+1<=self.m-1:
                    if [s_i,s_j+1] not in checked:
                        if tmp[s_i][s_j+1]==0:
                            confirmed+=[[s_i,s_j+1]]
                            checked.append([s_i,s_j+1])

바이러스가 너무 싫다. 하루빨리 사라졌으면 좋겠다.