[Python] 연구소1-3 / 완전탐색 - BFS와 조합

 

문제1. 연구소

 

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

https://www.acmicpc.net/problem/14502

14502번: 연구소

---

2. 핵심 아이디어

2-1) 벽을 세우는 모든 경우의 수를 계산

: 0이 위치한 좌표에서 3개의 조합만큼  벽을 세우는 모든 경우에 대해 테스트

=> 64C3으로 그렇게 해도 시간복잡도에 무리가 가지 않음

 

2-2) 벽을 세운 뒤 => 바이러스 퍼트리기

bfs 탐색을 통해 바이러스를 상하좌우를 탐색하여 0이라면 퍼트리기

 

2-3) 안전영역 최대값 갱신

: 벽을 세우는 경우에 대해 각 케이스의 안전영역을 계산하고

최댓값을 갱신하여 답 도출

---

3. 코드

#연구소
import sys
input = lambda: sys.stdin.readline().strip('\n')
from itertools import combinations
from collections import deque
import copy

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

def bfs(a,b):

  # 바이러스를 3으로 표시
  q= deque([(a,b)])
  data[a][b]=3

  while(q):
    x,y = q.popleft()

    for i in range(4):
      nx= x+dx[i]
      ny= y+dy[i]
		
      #상하좌우로 탐색한 값이 범위 안에 있는가? => 없으면 continue
      if nx<0 or ny<0 or nx>=n or ny>=m:
        continue
      
      #만약 인접한 칸이 0이라면 바이러스 퍼트리기(3으로 갱신)
      if data[nx][ny]==0:
        data[nx][ny]=3
        q.append((nx, ny))


#안전영역 카운트 함수 : 행마다 0의 개수를 셈
def cnt_zero():
  cnt=0
  for i in range(n):
      cnt+=data[i].count(0)
  
  return cnt


n,m = map(int, input().split())
zero=[]
data=[list(map(int, input().split())) for _ in range(n)]

#매 케이스마다 초기 맵에서 해야 하므로 복사본 떠놓기
data_copy= copy.deepcopy(data)

#벽을 세울 수 있는 공간 리스트로 받기
for i in range(n):
  for j in range(m):
    if data[i][j]==0:
      zero.append((i,j))

#벽을 세우는 케이스(3가지 조합)
zero_case = list(combinations(zero, 3))


result=0

for case1, case2, case3 in zero_case:
  data= copy.deepcopy(data_copy)
  
  #벽 세우기
  data[case1[0]][case1[1]]= 1
  data[case2[0]][case2[1]]= 1
  data[case3[0]][case3[1]]= 1

  for i in range(n):
    for j in range(m):
      if data[i][j]==2:
        bfs(i,j)
  
  #안전영역 카운트 최대값 갱신
  result= max(result, cnt_zero())

print(result)

---

4.배운점

브루트 포스를 적용할 수 있을지는 시간복잡도를 어림잡아 계산하여보면 된다.

조합을 이용하여 각 케이스를 만들고 맵을 매 케이스마다 비워주어야 한다는 것을 신경쓰자

---

문제2. 17141. 연구소2

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

https://www.acmicpc.net/problem/17141

17141번: 연구소 2

---

2. 핵심 아이디어

2-1) BFS+완전탐색 문제

: 탐색을 통해 가능한 조합을 모두 탐색하여 최소값 갱신

: 바이러스가 한번에 퍼져야 하므로 q 초기값이 바이러스들의 위치조합이 됨

 

2-2) 모두 퍼졌는지를 판단하는 기준

: 방문 안한 칸이 있음 + 그것이 벽이 아님(일반 칸이나 바이러스 칸) => 다 안퍼진 것

---

3. 코드

mport sys
input = lambda: sys.stdin.readline().strip('\n')
from collections import deque
from itertools import combinations
import copy

n,m= map(int, input().split())
data=[list(map(int, input().split())) for _ in range(n)]
virus=[]

#바이러스의 좌표 찾기
for i in range(n):
  for j in range(n):
    if data[i][j]==2:
      virus.append((i,j))
    
#m개의 조합 경우 만들기
virus_case= list(combinations(virus, m))

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


def bfs(_case):
  q=deque([])
  visited=[[-1]*n for _ in range(n)]
  m=0
  for i in _case:
    visited[i[0]][i[1]]=0
    q.append((i[0],i[1]))

  while(q):
    x,y= q.popleft()

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

      if nx<0 or ny<0 or nx>=n or ny>=n:
        continue
      
      # 방문하지 않았고 그것이 벽이 아니라면
      if (visited[nx][ny]==-1 and data[nx][ny]!=1):
          visited[nx][ny]= visited[x][y]+1
          q.append((nx, ny))
          m= max(m, visited[x][y]+1)

  for i in range(n):
      for j in range(n):
        if visited[i][j]==-1 and data[i][j]!=1:
          return float('INF')
  return m

result= float('INF')

#하나씩 이제 테스트 해보자
for _case in virus_case:
  result= min(result, bfs(_case))

if result==float('INF'):
  print(-1)
else:
  print(result)

---

4.배운 점

# visited 로 값을 갱신하며 data는 참고만 하면 copy모듈이 필요없음

# 필요조건이 아닌 여사건에 대한 정보는 유용하다

# data[i][j]==2 or data[i][j]==0이 아닌 data[i][j]!=1로 작성하므로 조건 단축화

---

문제3. 17142. 연구소3

 

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

---

2. 핵심 아이디어

2-1) 퍼질 수 있는 바이러스 M개의 조합 케이스를 하나씩 계산

: 바이러스 중 M개를 골라서 bfs를 통해 연구소1문제와 같이 퍼트리자 

: 초기 큐에 M개의 바이러스 위치를 모두 넣어주면 됨

 

2-2) 비활성 바이러스도 바이러스를 만나면 활성화됨

: 즉, 상하좌우 탐색값에서 0이 아닌 2에서도 바이러스는 퍼짐

 

2-3) 0초를 시작으로 퍼지는 시간을 맵에 갱신하자

초기 바이러스를 0초로 놓고 퍼지는 시간을

data[i] = data[now]+1 처럼 퍼지는 시간을 갱신해야 한다.

 

이때, 한번 방문한 값은 다시 방문하면 안되므로 visited배열을 통해

방문 정보를 기록해주자

 

2-4) 예외상황 주의점

: 바이러스가 비활성 바이러스와 만나는 시간은 최대 값이 되지 못한다.

 

예를 들어

다음 상황에서 비활성 바이러스와 만나는 시간이 5초이지만

이 시간은 최대값으로 계산되지 않아 4초로 답이 나와야 한다.

 

즉, 시간 초가 갱신되고 나서는 모든 바이러스와 벽의 위치는 -1로 초기화해주었다.

---

3. 코드

import sys
input = lambda: sys.stdin.readline().strip('\n')
from collections import deque
from itertools import combinations
import copy


n,m= map(int, input().split())
data=[list(map(int, input().split())) for i in range(n)]
virus=[] #바이러스 위치를 담을 리스트
wall=[] # 벽의 위치를 담을 리스트


#바이러스와 벽의 위치 잡기
for i in range(n):
  for j in range(n):
  	
    #바이러스라면 -> virus에 추가
    if data[i][j]==2:
      virus.append((i,j))
    
    #벽이라면 -> wall에 추가
    elif data[i][j]==1:
      wall.append((i,j))



data_copy= copy.deepcopy(data)

#m개의 virus 조합 만들기
virus_case = list(combinations(virus, m))

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

#맵을 퍼지는 시간으로 갱신
#매개변수 c는 바이러스 m개의 위치 조합
def bfs(c):
 q= deque()
	
 #매개변수로 들어온 위치조합을 모두 초기 큐에 넣어줌
 #초 수는 0으로 초기화 / 방문처리
 for i in c:
  q.append((i[0], i[1]))
  data[i[0]][i[1]]=0
  visited[i[0]][i[1]]=1

 while(q):
    x,y= q.popleft()

    for i in range(4):
      nx= x+dx[i]
      ny= y+dy[i]
      
      #인접 칸의 범위 확인
      if nx<0 or ny<0 or nx>=n or ny>=n:
        continue
	  
      #아직 방문하지 않았고 + 일반 칸 or 비활성 바이러스칸이라면 => 시간 갱신
      if visited[nx][ny]==0 and (data[nx][ny]==0 or data[nx][ny]==2):
        visited[nx][ny]=1
        q.append((nx, ny))
        data[nx][ny]=data[x][y]+1 # 지금 칸보다 1초뒤에 퍼짐


# 다 퍼졌는지 확인 하는 함수
def check():
  global result
  
  min_time=0
  
  for i in range(n):
  	#만약 안퍼진 칸 0이 있다면 -> return
  	if 0 in data[i]:
      return float('INF')
	
    min_time= max(min_time, max(data[i]))
    if min_time>=result:
      return float('INF')
      
  return min_time


result=float('INF')

for _case in virus_case:
  #맵과 방문정보 초기화
  data= copy.deepcopy(data_copy)
  visited=[[0]*n for _ in range(n)]
  
  # 이번 케이스에 대해 바이러스 시뮬레이션
  bfs(_case)
 
  #바이러스와 벽 위치는 모두 -1로 갱신시켜주기 => 예외상황 때문
  for i in virus:
    data[i[0]][i[1]]=-1

  for i in wall:
    data[i[0]][i[1]]=-1
  result= min(result, check())


#모두 퍼지는 경우가 한개도 없다면=> -1
#모두 퍼지는 경우가 있다면 => result 출력
if result ==float('INF'):
  print(-1)
else:
  print(result)

---

4.배운 점

바이러스를 0초시간 대에 동시에 퍼트리는 것에서 애를 먹었다.

=>초기 큐에 바이러스 위치를 모두 넣어주면 된다는 사실을 알게됨

 

또한 시간 대로 갱신시켰을 때 첫번째 예시 케이스에서 답이 4가 아닌 5가 나와 당황했다.

알고보니 비활성 바이러스에 닿는 5초의 순간이 계산에 포함되었었기 때문

=> 바이러스와 벽의 위치를 -1로 갱신해야 한다는 사실을 알게됨

 

바이러스와 벽으로밖에 이루어지지 않을 경우(예시3)

이때는 check 함수의 최댓값인 min_time=0으로 초기화되어

0이라는 알맞은 값이 나오도록 구성해놓았음