[백준 14502번] 연구소 -python

문제 링크

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

14502번: 연구소

 

풀이

- bfs 문제

- wall을 세울 수 있는 모든 경우의 수에 대하여 bfs로 안전 영역의 크기를 구한다 

# https://www.acmicpc.net/problem/14502
# pypy3로 하면 시간초과 안나지만 python3으로 하면 시간 초과 
# bfs 문제 
from collections import deque 
import copy
import sys

input = sys.stdin.readline

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

q = deque()

def bfs():
  global answer 
  # 그래프 복사 
  graph = copy.deepcopy(maps)
  
  # 바이러스 위치를 큐에 삽입 
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 2 :
         q.append((i,j))

  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 graph[nx][ny] == 0 :
        graph[nx][ny] = 2
        q.append((nx,ny))
  
  cnt = 0
  # 0인 곳 개수 구함 
  for i in graph:
    cnt += i.count(0)

  answer = max(answer, cnt)

def wall(x):
  # 벽 3개를 세웠으면 
  if x == 3 :
    bfs()
    return 
  
  for i in range(n):
    for j in range(m):
      # 벽을 새울 수 있는 곳이면 
      if maps[i][j] == 0:
        maps[i][j] = 1 
        wall(x+1)
        # 벽을 다시 돌려놈 
        maps[i][j] = 0 

n, m = map(int,input().split())

maps = []
answer = 0 

for _ in range(n):
  maps.append(list(map(int,input().split())))

wall(0)

print(answer)

+ 2022.04.12 다시 풀이 

- 조합으로 풀어보았다 

1. s에 벽을 세울 수 있는 인덱스의 위치를 삽입한다.

2. combinations를 사용하여 벽을 세울 수 있는 3개의 인덱스 조합 구한다. 

3. 조합 별로 해당 위치에 벽을 세우고 bfs 로 안전영역을 구한다. 

4. bfs 

1 ) 큐에 바이러스 위치를 대입한다.

2) 네 방향으로 이동하면서 바이러스가 퍼질 수 있는지 확인하고, 퍼질 수 있으면 해당 위치를 바이러스로 바꾸고 큐에 삽입 

3) 남은 0의 개수 (안전영역) 리턴 

5. 안전영역의 최댓값 갱신하고, 다시 벽 제거 

from itertools import combinations 
import sys, copy
from collections import deque 

input = sys.stdin.readline

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

def bfs():
	# 벽을 세운 그래프 복사 
    tmp_graph = copy.deepcopy(graph)
    ans = 0
    q = deque()
    # 바이러스의 위치 큐에 삽입 
    for i in range(n):
        for j in range(m):
            if tmp_graph[i][j] == 2:
                q.append((i,j))
                
    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 tmp_graph[nx][ny] == 0:
                tmp_graph[nx][ny] = 2 
                q.append((nx,ny))
                
    for i in tmp_graph:
        ans += i.count(0)
        
    return ans 
    
n, m = map(int,input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))
    
s = []

# 벽을 세울 수 있는 인덱스 구하기 
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0 :
            s.append((i,j))

# 벽을 세울 수 있는 인덱스 조합 구하기 
combine = list(combinations(s, 3))

result = 0
# 조합 별로 안전영역 크기 구하기 
for a,b,c in combine:
    graph[a[0]][a[1]] = 1
    graph[b[0]][b[1]] = 1
    graph[c[0]][c[1]] = 1
    result = max(result,bfs())
    graph[a[0]][a[1]] = 0
    graph[b[0]][b[1]] = 0
    graph[c[0]][c[1]] = 0

print(result)