[Python_DFS&BFS] 백준 14502번 : 연구소

1. 문제

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

14502번: 연구소

 

 

 

2. 풀이 과정

필요한 개념 : 조합, BFS

3개의 벽을 어디 세울지에 대해 조합을 사용하고, virus가 퍼지는 과정을 BFS를 통해 수행한다.

 

 

방법1) 재귀를 이용한 조합

 

import sys, copy, collections
input = sys.stdin.readline

n, m = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

graph = []
virus = []
fixed = 0
for i in range(n):
  row = list(map(int, input().split()))
  for j in range(m):
    if row[j] == 2:#바이러스 영역 저장
      virus.append((i,j))
    if row[j] == 1 or row[j] == 2:#벽과 바이러스의 수
      fixed += 1
  graph.append(row)
#입력받기 끝

#3개의 벽 선택(조합)
def select_wall(start, count):
  if count == 3:
    selected = copy.deepcopy(graph)
    safety_area(selected)
    return True
  else:
    for k in range(start, n*m):#start는 중복해서 선택하는 걸 방지
      a = k//m
      b = k%m
      if graph[a][b] == 0:
        graph[a][b] = 1
        select_wall(k, count+1)
        graph[a][b] = 0 #다시 벽 없애기

min_value = int(1e9)
def safety_area(g):
  global min_value
  #바이러스 퍼트리기
  c = 0
  q = collections.deque() 
  for v in virus:
    q.append(v)

  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<n and 0<=ny<m and g[nx][ny]==0:
        g[nx][ny] = 2
        q.append((nx, ny))
        c += 1

  #감염 지역 개수 세기
  min_value = min(min_value, c)

#함수 실행
select_wall(0, 0)
#(전체 칸의 수) - (초기 바이러스와 벽의 수) - (감염된 지역의 수) - (새로운 벽 3개) 출력
print(n*m - fixed - min_value - 3)

 

 

 

방법2) 반복문을 이용한 조합

- [방법1]과 시간복잡도 측면에서 큰 차이가 없다.

 

import sys, copy, collections
input = sys.stdin.readline

n, m = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

graph = []
virus = []
safety = []
fixed = 3 #새로운 벽 3개 미리 추가
for i in range(n):
  row = list(map(int, input().split()))
  for j in range(m):
    if row[j] == 2:#바이러스 영역 저장
      virus.append((i,j))
    if row[j] == 1 or row[j] == 2:#벽, 바이러스
      fixed += 1
    if row[j] == 0:
      safety.append((i, j))
  graph.append(row)
#

def select_wall():
  l = len(safety)
  for i in range(l):
    for j in range(i+1, l):
      for k in range(j+1, l):
        selected = copy.deepcopy(graph)
        selected[safety[i][0]][safety[i][1]] = 1
        selected[safety[j][0]][safety[j][1]] = 1
        selected[safety[k][0]][safety[k][1]] = 1
        safety_area(selected)

min_value = int(1e9)
def safety_area(g):
  global min_value
  #바이러스 퍼트리기
  c = 0
  q = collections.deque() 
  for v in virus:
    q.append(v)

  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<=nx<n and 0<=ny<m and g[nx][ny]==0:
        g[nx][ny] = 2
        q.append((nx, ny))
        c += 1

  #감염 지역 개수 세기
  min_value = min(min_value, c)

select_wall()
print(n*m - fixed - min_value)

 

 

 

방법3) 반복문 이용한 조합 + 지도를 1차원 배열로 표현

- 방법1, 2와 비교했을 때, 속도가 2배 향상됨

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
d = [-m, 1, m, -1] #상, 우, 하, 좌

graph = [] #전체 지도
virus = [] #바이러스 위치
safety = [] # 빈칸의 위치
fixed = 3 #새로운 벽 3개 미리 추가

for i in range(n):
  row = list(map(int, input().split()))
  for j in range(m):
    #바이러스 위치 저장
    if row[j] == 2:
      virus.append(i*m+j)
    #벽, 바이러스의 개수
    if row[j] == 1 or row[j] == 2:
      fixed += 1
    #빈칸 위치 저장
    if row[j] == 0:
      safety.append(i*m+j)
  graph += row #전체를 1차원 배열로 이어서 저장
#

def select_wall():
  l = len(safety)
  for i in range(l-2):
    for j in range(i+1, l-1):
      for k in range(j+1, l):
        selected = graph[:] #값 변경할거니까 복사해서 사용
        selected[safety[i]] = 1
        selected[safety[j]] = 1
        selected[safety[k]] = 1
        safety_area(selected)

min_value = int(1e9)
def safety_area(g):
  global min_value
  #바이러스 퍼트리기
  c = 0
  q = virus[:]

  while q:
    now = q[0]
    q.pop(0)
    for i in range(4):
      next = now + d[i]
      #범위 벗어나면 넘어가기
      #위
      if i==0 and now//m == 0:
        continue
      #우
      if i==1 and now%m==m-1:
        continue
      #아래
      if i==2 and now//m == n-1:
        continue
      #좌
      if i==3 and now%m==0:
        continue
      #범위 안 벗어나면 빈칸인지 확인
      if g[next]==0:
        g[next] = 2 #방문(감염됨) 표기
        q.append(next)
        c += 1 #감염된 지역 1증가

  #감염 지역 개수 세기
  min_value = min(min_value, c)

select_wall()
print(n*m - fixed - min_value)