[백준14502&파이썬] 조합과 BFS탐색을 적절히 활용하는 구현문제에서는 시작점에 대한 고민을 해보자

# 문제

백준 14502 연구소 파이썬 풀이

14502번: 연구소

# 코드

'''
  - 브루트 포스를 이용해 모든경우의 수에 벽을 다 세워보자
    - 64 * 63 * 62의 벽을 세울 수 있는 경우의 수가 생긴다. 25만
    - 벽을 세우고 바이러스를 퍼트린 후 안전영역을 카운팅 해야한다.
      - BFS를 이용해 완전 탐색을 할때 시간 복잡도
  - 백트래킹느낌으로 풀어봐야겠다.
'''
import sys
from collections import deque

def print2D(arr) :
  for i in arr :
    print(i)

DIRS = [
  (-1,0), (0,1), (1,0), (0,-1)
  ]

board = list()
N,M = map(int,sys.stdin.readline().split())

for _ in range(N) :
  line = list(map(int,sys.stdin.readline().split()))
  board.append(line)

mmax = 0
def dfs(wall_cnt) :
  global board
  global mmax

  if wall_cnt == 3 :
    # 벽이 3개모두 쳐짐, 안전영역의 크기를 구하고 max값을 업데이트
    dq = deque()
    visit = [[False] * M for _ in range(N)]
    for row in range(N) :
      for col in range(M) :
        if board[row][col] == 2 :
          dq.append((row,col))
          visit[row][col] = True

    while len(dq) != 0 :
      poped = dq.popleft()
      for dir in DIRS :
        next = (poped[0] + dir[0],poped[1] + dir[1])
        if 0<= next[0] < N and 0<= next[1] < M and visit[next[0]][next[1]] == False and board[next[0]][next[1]] == 0 :
          visit[next[0]][next[1]] = True
          dq.append(next)

    cnt = 0
    for row in range(N) :
      for col in range(M) :
        if visit[row][col] == False and board[row][col] == 0 :
          cnt+=1
    mmax = max(mmax,cnt)
    return

  for row in range(N) :
    for col in range(M) :
      if board[row][col] == 0 and wall_cnt <= 2 :
        # 백트래킹 사용
        board[row][col] = 1
        dfs(wall_cnt+1)
        board[row][col] = 0

dfs(0)
print(mmax)

# 풀이

• 문제에서 벽은 총 3가지의 경우로 칠 수 있었음에 주목했다.
• 벽이 형성되는 어떠한(?)조건이 있다면 그 조건을 이용해서 벽을 쳐보려 했지만, 아무리 생각해도 그런 조건이 떠오르지 않았다.
• 벽이 쳐질 수 있는 모든경우의 수(조합)를 구한 뒤에 벽을 쳐보는 형식으로 문제를 풀기로 했다. 

  for row in range(N) :
    for col in range(M) :
      if board[row][col] == 0 and wall_cnt <= 2 :
        # 백트래킹 사용
        board[row][col] = 1
        dfs(wall_cnt+1)
        board[row][col] = 0

• 위와 같이 현재 board에서 벽을 칠 수 있는 총 3가지의 조합을 구하기 위해서 백트래킹을 사용했다. 
• wall_cnt가 3이 된다면 해당 시점에서는 BFS로 바이러스를 퍼트린후 0의 개수를 구하도록 했다.

## 개선 가능한 부분

• 먼저 3가지의 벽이 쳐지는 좌표의 조합을 구하는 것을 itertools의 combinations을 이용하면 손쉽게 벽을 칠 수 있는 조합을 구할 수 있다.
  • 그러나 경험상 메모리와 시간을 더 잡아 먹기는 한다.
• " wall_cnt == 3 " 즉, 벽이 3개가 될때마다 현재 board를 기준으로 바이러스의 시작점(2)을 찾고 deque에 넣는 불필요한 과정이 반복된다.
• 애초에 입력부터 2인부분을 찾아놓고 저장시켜 놓고 wall_cnt가 3이 될때마다 이 바이러스의 시작점(2)을 재활용한다면 시간을 더 줄일 수 있다.