골드 V

💡문제 분석 요약

BFS, 백트래킹, 브루트포스

💡알고리즘 설계

3개의 벽을 세우고 세웠을 때 안전구역을 센다.

여러 경우의 수 중에서 안전구역이 가장 큰 것을 return한다.

여기서 3개의 벽을 세우는 방법은 2가지다.

  1. 백트래킹

  2. combinations를 활용한 모든 경우 탐색하기.

  3. 백 트래킹
    1. return조건을 세운다.
      1. 벽을 3개 설치하고, 안전구역을 다 셌을 경우 return한다.
      2. return으로 돌아 왔을 때 세운 벽을 없앤다. 0으로 다시 바꾼다.
    2. 벽을 세울 수 있는 0이면 1로 변환시켜 벽을 세운 뒤, 벽의 갯수를 넣고 함수를 호출한다.

💡코드

import sys
from collections import deque
import copy
dx = [0,0,1,-1]
dy = [1,-1,0,0]
answer =0
input = sys.stdin.readline
n,m = map(int,input().strip().split(' '))

maps = []

for i in range(n):
    sample = list(map(int,input().strip().split(' ')))
    maps.append(sample)    

# 벽 세우기
def makewall(wall):

    if wall==3:
        find_virus()
        return 
    
    for i in range(n):
        for j in range(m):
            if maps[i][j]==0:
                maps[i][j]=1
                makewall(wall+1)#return시 돌아옴
                maps[i][j] = 0#0으로 초기화 그다음 j+1탐색

def find_virus():
    visited = [[0 for _ in range(m)] for _ in range(n)]
    temp_maps = [row[:] for row in maps]
    #copy.deepcopy로 완벽히 복사 할 수 있지만,
    #2차원이라 가능하며 일단 속도가 느림. 
    queue = deque()
    for i in range(n):
        for j in range(m):
            if temp_map[i][j]==2:
                queue.append([i,j])
    
    
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (0<=nx<n) and (0<=ny<m) and not visited[nx][ny] and temp_map[nx][ny] ==0:
                temp_map[nx][ny] =2
                queue.append([nx,ny])
                visited[nx][ny] = 1

    safe_area = 0
    #안전구역 탐색
    for i in range(n):
        safe_area+= temp_map[i].count(0)
    global answer
    answer = max(safe_area,answer)

makewall(0)
print(answer)

💡틀린 이유

  • bfs로 안전구역 탐색은 알겠으나, 막상 3개의 벽을 세우려니 머리가 아팠음.. 그냥 가능한거 다 탐색하면 될걸..ㅜㅜ

💡 기억할 것

  • back tracking은 dfs와 비슷하지만 특정 조건에 부합하지 않으면 탐색하지 않고 돌아간다. 따라서 dfs보다 탐색공간을 줄인다.
  • DFS의 return이후의 행동과 return조건을 잘 생각하자