문제

처음 보고 든 생각

• 이거 BFS,,, DFS,,,, (다 까먹음)
• 세로와 가로 길이가 작다 (3 ≤ N, M ≤ 8). greedy하게 풀 수도있겠다
  • 시간복잡도 계산 후, 안될것같으면 DFS, BFS 복습후 이렇게 푸는 방법 해보자

시간복잡도 계산
가장가장 생각없이 풀었을때를 가정하자 (3 ≤ N, M ≤ 8)

• 벽1이 있을 수 있는 위치 경우 : n*m
• 벽2의 있을 수 있는 위치 경우 : n*m
• 벽3의 있을 수 있는 위치 경우 : n*m
• 한 케이스에서 얼만큼의 유효공간이 나오는지 계산
  • 벽이 없는 곳에 다 감염시킴 : n*m
  • 유효공간 체크 : n*m

➡️ 총 O(N*M)^4 $\sim$ 12^4 $\sim$ 20736
뭐여 이거 걍 구현아니여?

구현해보자

def print_arr() :
	for line in A :
		print(line)
	print()


def solution(x, y) :
	global N, M, is_three_cnt

	if (x== N or y == M) : # 탐색 종료 (마지막줄이거나 마지막칸일때)
		return

	print('====checking %d,%d====' %(x,y))
	print_arr()

	if (A[x][y] != 0) : # 벽을 세울 수 없는 경우
		return

	# 벽세우기
	A[x][y] = 1
	is_three_cnt += 1

	print('new wall has done!')
	print_arr()

	if (is_three_cnt == 3) : # 3개 벽을모두 세운 경우
		res_arr.append(calc_safety()) # 안전영역을 계산하여 저장한다
		A[x][y] = 0
		is_three_cnt -= 1
		print('three has done!\n')

	if (y == M-1) : # 한 줄을 넘어갈때 다음줄 탐색
		solution(x+1, 0)
	else :
		solution(x, y+1)

	# 벽 세운것 다시 uncheck
	A[x][y] = 0
	is_three_cnt -= 1


#N, M =map(int,input().split())
#A = [list(map(int,list(input()))) for _ in range(N)]

N, M = 3,3
A = [[0,0,0], [0,0,0], [0,0,0]]
is_three_cnt = 0
res_arr = []

solution(0,0)


print(max(res_arr))

구조를 greedy랑 dfs로 나눌 수 있다.

• 재귀함수 solution
  • 큰 구조로는 벽을 3개 세울 수 있는 경우 = greedy하게 셈
• calc_safety()
  • 바이러스를 퍼졌을때 감염범위 세기 = dfs로 셈

이다.

구현하다보니 그렇게 간단하지 않았다.
너무 복잡해져서, 더 간단하게 하고 & 더 빨라질 수 있는 레퍼런스를 찾아봤다

개선 아이디어

• 벽 탐색시 : greedy하게 탐색시 2차원 배열을 인덱스 두개로 접근하는게 아니라, 1차원 배열처럼 인댁스 한개로 접근.

		for i in range(start, N*M) : 
			r = i // M # 행 = M으로 나눈 몫
			c = i % M # M으로 나눈 나머지는 열 

(3 ≤ N, M ≤ 8) 이니 일차원 배열로 쳐도 무방하고, 코드도 훨씬 단순해졌다!

• dfs : 감염범위를 따지는건 이코테 책의 아이스크림 문제를 참고하자
• deep_copy : copy라이브러리의 deep_copy를 사용해서 배열을 통채로 복사
• 이차원 배열 빠른 count : safe_count = sum(_.count(0) for _ in sel_wall) # 안전영역수 계산 한줄로 잘 정리하는 습관을 들이자

개선 코드

import sys
import copy

res_arr = []
dx, dy = [-1,1,0,0], [0,0,-1,1] # 상하좌우 이동
N, M =map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)] # 그래프 생성
A_copy = copy.deepcopy(A) # 그래프 복사

# dfs
def dfs(x, y, sel_wall) :
	sel_wall[x][y] = 2 # 바이러스로 변경

	# 상하좌우 탐색
	for i in range(4) :
		nx, ny = x + dx[i], y+dy[i]
		if 0 <= nx < N and 0 <= ny < M : #조건1) 그래프 범위 내에 있으면서
			if sel_wall[nx][ny] == 0 : # 조건2) 바이러스가 퍼질 수 있을때
				dfs(nx, ny, sel_wall)

def calc_safety(A_copy) :
	global N, M
	sel_wall = copy.deepcopy(A_copy)
	# dfs로 바이러스 퍼트리기
	for i in range(N) :
		for j in range(M) :
			if sel_wall[i][j] == 2 : #바이러스 발견시 dfs
				dfs(i, j, sel_wall)
	return (sum(_.count(0) for _ in sel_wall)) # 안전영역수 계산

def solution(start, is_three_cnt) :
	global N, M

	if (is_three_cnt == 3) : # 3개 벽을모두 세운 경우
		res_arr.append(calc_safety(A_copy)) # 안전영역을 계산하여 저장한다
		return
	else : # 벽이 3개 선택되지 않은 경우
		for i in range(start, N*M) :
			r = i // M # 행 = M으로 나눈 몫
			c = i % M # M으로 나눈 나머지는 열
			if A_copy[r][c] == 0 : # 해당구역이 0인 경우
				A_copy[r][c] = 1 # 벽을 세움
				solution(i, is_three_cnt+1)
				A_copy[r][c] = 0 # 되돌리기


solution(0,0)
print(max(res_arr))

결과

오예

레퍼런스

개선 아이디어 얻은 블로그