백준 14502 문제 - 연구소

이전 작성한 글에서 DFS의 활용과 백트래킹을 다루었는데, 14502 백준 문제와 연관이 있다.

14502번: 연구소

 

문제

백준 14502

구하고자 하는 것은 바이러스가 퍼지고 난 후, 최대 안전 영역이다.

처음에는 벽 세 개를 어떻게 뽑지? 생각이 들었다. 조합을 생각할 수 있는데 여기서 DFS 활용을 적용할 수 있다.

일단 벽을 세 개 세웠을 때 모든 경우에서 바이러스가 퍼지고 난 후 면적을 모두 구하고 비교하는 방식으로 문제를 풀 수 있다.

최대 조합이 64개 중 3개 뽑는 조합으로, 10만 보다 작은 수이므로, 모든 경우의 수를 고려해도 제한 시간(이 문제는 2초) 안에 문제를 해결 할 수 있다.

(일반 컴퓨터에서 C언어로 기준으로 10억개이상의 연산 횟수를 넘어가면 1초 이상의 시간이 소요된다) => '이코테' 책 참조.

 

먼저 문제를 풀기 위해서 필요한 것은,

1. 벽을 세 개 세운다. => DFS 조합 적용

2. 벽에 3개가 되었을 때, 바이러스를 퍼뜨리는 함수 필요  => DFS 이용

3. 바이러스가 다 퍼지고 난 후, 해당 경우의 면적을 구하고 max를 이용해서 최대 안전 영역 구하기 => 0의 개수 구하면 됨

 

코드

n, m = map(int, input().split())
data = [] # 초기 맵
temp = [[0] * m for _ in range(n)] # 벽 설치 후 맵

for _ in range(n):
	data.append(list(map(int, input().split())))
   
# 북 동 남 서 이동 방향 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

#DFS를 이용해서 각 바이러스가 사방으로 퍼지도록 하기

def virus(x,y):
	for i in range(4):
    	nx = x + dx[i]
        ny = y + dy[i]
        #상, 하 , 좌, 우 중에서 바이러스가 퍼질 수 있는 경우
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
        	if temp[nx][ny] == 0:
            #해당 위치에 바이러스 배치하고 다시 재귀적으로 수행
            		temp[nx][ny] = 2
            		virus(nx, ny)


# 현재 맵에서 안전 영역 크기 구하기
def getScore():
	score = 0
    for i in range(n):
    	for j in range(m):
        	if temp[i][j] == 0:
            		score += 1
    return score

# DFS를 이용해서 벽 설치 와 벽이 세 개가 되었을 때, 바이러스 함수 호출 후 안전 영역 크기 계산
def dfs(count):
	global result
    # 벽이 세 개 일 때
    if count == 3:
    	for i in range(n):
        	for j in range(m):
            		temp[i][j] = data[i][j]
        # 바이러스 전파       
        for i in range(n):
        	for j in range(m):
            		if temp[i][j] == 2:
                		virus(i,j)
        # 안전 영역 최대 크기 계산
        result = max(result, getScore())
        return
    # 빈 공간에 벽 설치
    for i in range(n):
    	for j in range(m):
        	if data[i][j] == 0:
            		data[i][j] = 1
                	count += 1
               	 	dfs(count)
                	data[i][j] = 0
               	 	count -= 1

dfs(0)
print(result)​