문제

입출력

• 제한
  • 시간 2초 / 메모리 512MB
• 입력
  • 첫째줄 : 세로 N, 가로 M
    (3<=N, M<=8)
  • 둘째줄~ : 지도 모양.
    0 = 빈칸 / 1=벽 / 2=바이러스
    (2<=2의 갯수<=10)
• 출력
  • 얻을 수 있는 안전 영역의 최대 크기 출력

상황

0 = 빈칸 / 1=벽 / 2=바이러스일때,

• 바이러스는 벽이 없는 곳으로 퍼져감
• 바이러스가 퍼지지 않는 안전 영역 최대 크기 구하시오

풀이

당위성

• 가능한 모든 경우의 수를 계산해도 시간제한을 넘어가지 않음을 게산가능해야
• 덩어리구하기 = DFS 임을 이해한다.

풀이 아이디어

1. 초기 비어있는 모든 공간 중 3개를 골라 벽을 설치 (브루트포스)
2. 설치 후, 안전 영역 구하기 (DFS/BFS)
3. 1~2 반복한 후, 최대 안전영역 크기 출력하기

시간복잡도

• 최대 전체 크기가 8*8 이므로
• 벽을 설치할 수 있는 모든 조합의 수는 최악의 경우 (바이러스가 하나도 존재 X) $_{64}C_3$ 이다.
• 100,000 보다 작은 수이므로, 모든 수를 고려해도 제한 시간 안에 문제를 해결 할 수 있다.

소스코드

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())))

# 4가지 이동 방향에 대한 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0

# DFS를 이용하여 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y) :
	for i in range(4) :
		# 갈 수 있는 예비선택지 nx, ny
		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 get_score() :
	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
	# 울타리가 3개 설치된 경우
	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, get_score())
		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)

느낀점

• 울타리를 치는 모든 경우의 수를 어떻게 구하지,, 했는데 한 DFS안에 때려박아서 만들 수 있구나