연구소[백준14502] - python

 

정답 코드 

import sys 
import copy
from collections import deque
from itertools import combinations
input = sys.stdin.readline
directions = [[1,0], [-1,0], [0,1], [0,-1]]

def bfsAndCountZero(array, viruses) :
  height = len(array)
  width = len(array[0])
  visited = [[0] * width for _ in range(height)]
  zero_count = 0

  queue = deque()
  for virus in viruses :
    queue.append(virus)

  while queue :
    curr_x, curr_y = queue.pop()
    for dir in directions :
      dir_x, dir_y = dir
      next_x = curr_x + dir_x
      next_y = curr_y + dir_y
      
      if next_x < 0 or height <= next_x or next_y < 0 or width <= next_y :
        continue
      
      if visited[next_x][next_y] :
        continue

      if array[next_x][next_y] == 0 :
        array[next_x][next_y] = 2
        visited[next_x][next_y] = 1
        queue.append([next_x, next_y])

  for x in range(height) :
    for y in range(width) :
      if array[x][y] == 0 :
        zero_count += 1
  
  return zero_count


def BOJ14502() :
  N, M = map(int, input().split())
  graph = []
  for _ in range(N) :
    graph.append(list(map(int, input().split())))
  
  virus_list = []
  empty_list = []
  answer = 0
  
  for x in range(N) :
    for y in range(M) :
      if graph[x][y] == 2 :
        virus_list.append([x,y])
      elif graph[x][y] == 0 :
        empty_list.append([x,y])
  
  empty_combinations = list(combinations(empty_list, 3))
  
  for empties in empty_combinations :
    for empty in empties :
      x, y = empty
      graph[x][y] = 1

    temp_graph = copy.deepcopy(graph)
    answer = max(answer, bfsAndCountZero(temp_graph, virus_list))

    for empty in empties:
      x, y = empty
      graph[x][y] = 0

  print(answer)

BOJ14502()

 

문제 접근 

1. 벽을 세우는 방법들의 조합을 구하자(combinations 라이브러리 사용)

2. 조합의 경우의 수에 맞춰 지도에 임시로 가벽을 세워버리고 그 채로 bfs and Count 적용

3. 다시 지도에서 임시 가벽을 없애고 다시 들어간다 

4. 최댓값 찾기

 

 

인사이트

1. deepCopy의 개념이 필요했는데 직접 찾아 적용하게 되었다

2. 맨처음에 bfs내부에서 뭘 잘못했는지 탐색이 원하는 대로 되지 않았다(결국 다 지우고 다시 짰다)

3. bfs 내부의 if문을 가독성이 더 좋게 짜보려 했다. 부정문을 먼저 두어 탈출 하게 하였다

4. 난이도가 어려운 문제는 아닌데 처음에 너무 두서 없이 짜서 제 발목을 잡은것 같다. 

 

 

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

14502번: 연구소