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

🎉 문제

 

 

 

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

 

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

 

 

🎉 풀이

✅ 다행히 n, m 크기가 8밖에 안돼서 조합 이용이 가능했다 . . .조합 이용할 예정이라면 시간 복잡도 계산 잘 해야 한다 !

✅ 처음 입력받은 연구소 상태를 계속 이용해야 하므로 deepcopy 활용

✅ 벽을 세우고 나서 연구소 상태를 dfs로 체크하면서 최대 안전지역 갱신

 

🎉 코드

import itertools, copy


def infection(groundcopy, j, k, visited, n, m):
	#감염 시킨 곳이라고 방문체크
    visited[j][k] = True

	#상 우 하 좌 순서로 탐색
    di = [-1, 0, 1, 0]
    dj = [0, 1, 0, -1]

    for d in range(4):
        ni = j + di[d]
        nj = k + dj[d]
		
        #범위 안에 포함될 때
        if 0 <= ni < n and 0 <= nj < m:
        	#아직 감염 방문 하지 않았고, 감염할 수 있는 곳(벽도 아니고 이미 감염된 곳도 아닌 연구소)이라면
            if not visited[ni][nj] and groundcopy[ni][nj] == 0:
            	#감염시키고
                groundcopy[ni][nj] = 2
                #연구소에 또 감염시킬 데 있는지 탐색하러 갑니다
                infection(groundcopy, ni, nj, visited, n, m)






#연구소의 세로 크기 n, 가로크기 m 입력받기
n, m = map(int, input().split())

#연구소 상황 입력 받기
ground = [list(map(int, input().split())) for _ in range(n)]

#벽을 세울 가능성이 있는 위치 담을 리스트
groundlist = []

#벽을 세울 수 있는 곳이면 리스트에 담기
for i in range(n):
    for j in range(m):
        if ground[i][j] == 0:
            groundlist.append([i, j])

#벽을 세울 세 위치를 조합하여 리스트로 담아두기
combinationlist = list(itertools.combinations(groundlist, 3))

#안전 영역의 최댓값
answer = 0

#벽을 세울 수 있는 위치 조합 리스트를 순서대로 탐색해볼까요?
for i in range(len(combinationlist)):
	#원본 배열은 두고 벽을 세울 위치만 다르게 한 연구소를 탐색해야 하므로 원본배열의 훼손이 일어나지 않는 copy.deepcopy를 사용해서 복사 
    groundcopy = copy.deepcopy(ground)
    #벽 세우기
    for j in range(3):
        a, b = combinationlist[i][j]
        groundcopy[a][b] = 1

	#감염 방문 체크를 할 배열 생성
    visited = [[False] * m for _ in range(n)]
    for j in range(n):
        for k in range(m):
            if not visited[j][k] and groundcopy[j][k] == 2:
            	#연구소 감염 진행
                infection(groundcopy, j, k, visited, n, m)

	#감염된 연구소 groundcopy가 생성되었으니 안전 영역을 카운트 합니다
    cnt = 0
    for j in range(n):
        for k in range(m):
            if groundcopy[j][k] == 0:
                cnt += 1
	
    #안전 영역 크기의 최대값을 갱신합니다
    answer = max(answer, cnt)

print(answer)