[백준 파이썬] #14502. 연구소

풀기 전 생각해보기😮

• 벽을 세울 수 있는 곳 중에서 세곳을 선택하고 벽을 세운다
• 벽을 세운 후 바이러스가 확산되었을 때, 확산되지 않은 방의 개수를 확인한다
• 다른 세 곳에도 벽을 세울 수 있는 모든 경우에 대해 확인한다
• 확산되지 않은 방이 가장 큰 경우를 선택한다

 

• 바이러스의 확산을 확인하기 위해 BFS를 사용했다
• deepcopy 방식을 이용해서 매 경우 마다 사용하는 arr를 초기화 시켜주었다

---

풀이🛫

# 완전 탐색, BFS

from collections import deque

# U,R,D,L
dcol = [-1,0,1,0]
drow = [0,1,0,-1]

# BFS: 바이러스의 확산
def spread_virus(lst):
    global virus    # 바이러스가 있는 방 정보 가져오기

    queue = deque(virus)
    while queue:
        col, row = queue.popleft()
        for v in range(4):
            ncol = col + dcol[v]
            nrow = row + drow[v]
            if 0<=ncol<N and 0<=nrow<M and lst[ncol][nrow] == 0:
                lst[ncol][nrow] = 2     # 바이러스 확산 표시
                queue.append((ncol, nrow))      # BFS 탐색 전개를 위해 큐 append
    return


def comb(level, start, temp):   # level: 깊이, start: 인덱스 기준, temp: 저장공간
    if level == 3:      # 원하는 깊이에 도달할 때 = 원하는 만큼 담았을 때
        arr_copy = [arr[i][:] for i in range(N)]    # arr 행에 대해서 n개의 슬라이싱 복사 = deepcopy
        cnt = 0     # 안전한 공간의 개수 저장공간
        # 벽을 세우는 작업 진행
        for c, r in temp:
            arr_copy[c][r] = 1


        # 바이러스가 퍼졌을 때 남아있는 방 개수 확인
        spread_virus(arr_copy)
        for col in range(N):
            for row in range(M):
                if arr_copy[col][row] == 0:      # 안전한 공간일 경우
                    cnt += 1                # cnt += 1

        # 정답 리스트에 push 후 초기화
        ans_lst.append(cnt)

        return          # 재귀의 return

    # 조합: 한번 뽑았던 인덱스는 다시 뽑지 않아야 해
    # 뽑은 요소는 temp에 push
    for s in range(start+1, len(possible)):
        comb(level+1, s, temp+[possible[s]])


N, M = map(int, input().split())    # N: 세로, M: 가로
arr = list(list(map(int, input().split())) for _ in range(N))     # 0: 빈칸, 1: 벽, 2:바이러스
possible = []
virus = []
ans_lst = []

# 벽을 세울 수 있는 모든 공간 담기
for col in range(N):
    for row in range(M):
        if arr[col][row] == 0:
            possible.append((col, row))
        elif arr[col][row] == 2:
            virus.append((col, row))

# 3곳을 뽑아서 진행
comb(0, -1, [])

print(max(ans_lst))

 

핵심 정리🎁

# 슬라이싱을 이용한 깊은 복사
# arr의 i열에 대해서 행을 복사
copy_arr = [arr[i][:] for i in range(N)]

# deepcopy 메서드를 이용할 수도 있다
import copy
copy_arr = copy.deepcopy(arr)


# 조합을 이용한 완전탐색
def comb(level, start, temp)
    if level == 3:	# 목표했던 깊이에 도달했을 때
	# 원하는 작업에 대한 코드 입력
        return		# 이전 깊이로 return

    # start+1: 한번 선택한 인덱스(start)를 다시 뽑지 않고 이후의 인덱스를(start+1) 탐색하도록 함
    # len(possible): 벽을 세울 수 있는 모든 범위
    for s in range(start+1, len(possible)):
        # 깊이를 1 증가, start+1 ~ len(possible) 범위의 값(possible[s])를 temp 공간에 append 하고 dfs 진행
        comb(level+1, s, temp+[possible[s]])

링크💎

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

14502번: 연구소