python 백준14502 연구소(BOJ14502)

문제링크 : https://www.acmicpc.net/problem/14502

14502번: 연구소

이문제는 아이디어 떠올리는 데만 2시간이 걸린것같다..아이디어를 떠올리는게 정말 어려웠다

혹시나 아이디어만 얻기위한 사람이 있을수 있어서 내가 풀었던 아이디어만 먼저 공유한다

문제해결 아이디어

1) 연구소 지도에서 벽 3개를 세운다

2) 벽을 세운 지도로 바이러스 확산 시뮬레이션을 해본다

3) 시뮬레이션 후 빈공간 갯수를 비교해본다

4) 1~3번 과정을 모든 경우의 수 만큼 반복

 

아래 코드도 처음 통과했던 코드는 아니고 통과하고나서 조금 수정했다

사실 여기서 더 수정하려고한다면 빈공간 좌표만 따로 만들어두고 그걸 기준으로 조합해서 벽을 세우거나

조합라이브러리를 사용해서 벽을 세운다거나 여러가지가 있지만

실제로 그렇게 해서 제출해보니 메모리나 소요시간이 큰 차이가 없었다

그래서 그냥 개인적으로 가장 이해하기 편한 코드를 기준으로 여기에 적어둔다

#bfs사용하기위한 deque추가
from collections import deque

#세로 n 가로 m
n, m = map(int, input().split())

#연구소 지도
lab_map = []
for _ in range(n):
  lab_map.append(list(map(int, input().split())))

#상하좌우 좌표값
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

#바이러스 확산 함수
def virus(x,y, simul_map):
  #bfs로 확산
  queue = deque()
  queue.append((x,y))
  #큐가 비워질때까지 계속 확산
  while queue:
    x, y = queue.popleft()

    #상하좌우 체크
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      #지도 밖이면 패스
      if nx < 0 or nx >= n or ny < 0 or ny >= m:
        continue
      #공간이 빈칸일때 확산 하고 큐에 추가
      if simul_map[nx][ny] == 0:
        simul_map[nx][ny] = 2
        queue.append((nx,ny))

#연구실 내 모든 바이러스 확산 시뮬레이션
def simulation(simul_map):
  #바이러스 전파 테스트
  for i in range(n):
    for j in range(m):
      if simul_map[i][j] == 2:
        virus(i,j, simul_map)
        
  #빈공간 갯수 카운트
  result = 0
  for i in range(n):
    for j in range(m):
      if simul_map[i][j] == 0:
        result += 1
  return result

#최대 크기 계산
def cal():
  max_val=0
  #연구소 지도에서 모든 경우의 수로 벽 3개를 세운다
  for i in range(n*m - 2):
    for j in range(i + 1, (n*m)-1):
      for k in range(j + 1, (n*m)):
        
        #연구소 지도 복사(원본이 수정되는걸 방지)
        simul_map = []
        for l in range(n):
          simul_map.append(lab_map[l][:])
          
        #하나라도 빈공간이 아니라면 패스
        if simul_map[i//m][i%m] == 0 and simul_map[j//m][j%m] == 0 and simul_map[k//m][k%m] == 0:
          #벽세우기
          simul_map[i//m][i%m] = 1
          simul_map[j//m][j%m] = 1
          simul_map[k//m][k%m] = 1

          #세워진 벽을 기준으로 시뮬레이션 결과 비교
          simulation_result = simulation(simul_map)
          if simulation_result > max_val:
            max_val = simulation_result
  #빈공간 최대갯수 리턴
  return max_val

print(cal())