[백준/알고리즘/python/java] 14502번 - 연구소

이미지를 누르면 문제 링크를 보실 수 있습니다.

이미지를 누르면 문제 링크를 보실 수 있습니다.

 

이 문제는 DFS와 BFS를 결합한 흥미로운 접근 방식을 요구합니다. 

이 문제의 핵심은 "가능한 한 많은 영역을 안전하게 보호하는 벽의 배치를 찾는 것" 입니다. 여기서 주목해야 할 점은 "모든 벽의 조합을 시도"해보고, "각 경우에 대해 바이러스가 얼마나 퍼지는지를 시뮬레이션"해야 한다는 것입니다. 이를 위해서 DFS를 사용해 벽을 세우고, BFS로 바이러스의 확산을 시뮬레이션합니다.

 

초기 접근 방법은 아래와 같습니다.

from collections import deque
import sys
input = sys.stdin.readline


# 벽을 3개를 세운다.  -> 모든 경우의 수를 다 세어본다 : dfs
# 바이러스를 퍼뜨려본다.
# 0의 개수를 구한다.
# 이 값을 max값과 계속 비교하면서 최댓값을 구한다.


def bfs():

    queue = deque()
    visited = [[False] * m for _ in range(n)]
    area = 0

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 2:
                queue.append([i,j])
                visited[i][j] = True

    while queue:

        r,c = queue.popleft()

        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if 0 <= nr < n and 0<= nc < m and not visited[nr][nc] and graph[nr][nc] == 0:
                visited[nr][nc] = True
                queue.append([nr,nc])

    # 안전영역의 개수 구하기
    # 0 이면서 && 바이러스가 들르지 않은 곳 = > 안전영역
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0 and not visited[i][j]:
                area += 1

    return area

def dfs(index):
    global cnt

    if index == 3:
        # 바이러스를 퍼뜨려본다.
        countOf0 = bfs()
        # 남아있는 0의 개수를 센다.
        cnt = max(cnt, countOf0)
        return  # index 3 이 되면 해당 dfs 종료 - 최종적으로 갱신된 cnt가 답

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1 # 벽을 세워 보고
                dfs(index+1)    # 넘긴다.
                graph[i][j] = 0 # 벽을 다시 치워 준다.

n,m = map(int,input().split())

graph = []
for i in range(n):
    graph.append(list(map(int,input().strip().split())))

global cnt
cnt = 0

dr = [-1,1,0,0]
dc = [0,0,-1,1]

dfs(0)
print(cnt)



위 코드에서는 결국 시간초과가 발생하였는데, 

1. 가능한 모든 벽의 조합을 시도하는 부분("DFS")
2. 그 후에 각 조합에 대해 "BFS"를 실행하는 부분

에서 비효율적인 계산이 있기 때문일 가능성이 큽니다.

 

이 문제를 효율적으로 해결하기 위한 몇 가지 개선 방법은 아래와 같습니다.

1. 벽을 세울 위치 선정 최적화 : 가능한 모든 위치에서 벽을 세우는 대신, 빈 공간(0)위치만을 대상으로 벽을 세우는 경우를 고려합니다. 이를 위해 빈 공간의 위치를 미리 리스트에 저장해 두고, 그 리스트를 사용하여 벽을 세우는 위치를 결정합니다.
2. BFS 최적화 : BFS를 수행할 때, 매번 새로운 'visited' 배열을 생성하는 대신, 원래의 'graph' 배열을 복사하여 사용하거나, 기존 'graph' 배열에 임시로 바이러스를 퍼뜨리고 나중에 다시 원상태로 복구하는 방법을 사용할 수 있습니다.
3. 조기 종료 : 안전 영역의 개수가 현재까지 발견된 최대 안전 영역 개수보다 작거나 같을 경우, 더 이상의 계산을 중단하고 다음 조합으로 넘어갈 수 있습니다. 

다음은 개선된 코드입니다.

from collections import deque
import sys
input = sys.stdin.readline
import copy


n, m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]

dr = [-1,1,0,0]
dc = [0,0,-1,1]

# 빈 공간 위치 화인
empty_space = [(i,j) for i in range(n) for j in range(m) if graph[i][j] == 0]
max_area = 0

def bfs():
    
    temp_graph = copy.deepcopy(graph)	# 기존 graph를 deepcopy	
    queue = deque()	
    
    for i in range(n):
        for j in range(m):
            if temp_graph[i][j] == 2:
                queue.append((i,j))		# 바이러스가 있는 부분을 queue에 저장
    
    while queue:		# 	queue가 빌 때 까지
        
        r, c = queue.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            # 바이러스를 퍼뜨릴 수 있는 곳이라면, 해당 위치를 2(바이러스)로 바꾼다.
            if 0 <= nr < n and 0<= nc < m and temp_graph[nr][nc] == 0:
                temp_graph[nr][nc] = 2
                queue.append((nr,nc))	# 계속 퍼뜨리기 위해 queue에 추가
    
    # 다 퍼뜨렸으면, temp_graph에서 남아있는 0의 개수 구하기 -> 안전 영역 구하기
    return sum(row.count(0) for row in temp_graph)
    
def dfs(count,start):
    global max_area
    
    if count == 3:	# 벽이 3개가 세워졌으면, 해당 시뮬레이션 종료
        max_area = max(max_area,bfs())	# 바이러스 퍼뜨려서 최대 안전 영역 구하기 -> 갱신
        return 

    for i in range(start,len(empty_space)):	# 기존에 저장했던 empty_space를 순회하면서
        r,c = empty_space[i]
        graph[r][c] = 1		# 벽을 세워보고
        dfs(count+1,i+1)	# 넘긴다
        graph[r][c] = 0		# 벽을 다시 치워준다

dfs(0,0) # 0개의 벽, empty_space 리스트의 0번째 원소 부터 start
print(max_area)

 

이 코드에 대한 로직은 주석으로 표시했습니다. 코드를 짤 때, 주목해야 할 몇 가지 포인트는 다음과 같습니다.

• 벽 세우기 : 모든 빈공간에 대해 세 개의 벽을 세우는 모든 조합을 시도합니다. 이 때, 중복을 피하기 위해 이전 벽 이후의 위치부터 탐색을 시작합니다.
• 바이러스 확산 시뮬레이션 : 각 벽 조합마다 바이러스의 확산을 시뮬레이션 합니다. 이 때, BFS를 사용하여 각 바이러스 위치에서 상하좌우로 퍼져나갈 수 있는 지점을 탐색합니다.
• 시간 효율성 : 초기 코드에서 시간초과 문제가 발생했던 부분을 개선하기 위해, 빈 공간 리스트를 미리 만들고, 바이러스 확산 시 'deepcopy'를 사용하여 원본 'graph'를 보호합니다.

다음은, 문제를 푸는 과정에서 짚고 넘어갈 파이썬 문법 팁에 대해 설명드리겠습니다.

 

- 깊이우선탐색(DFS) 와 재귀-

• 이 문제에서 DFS는 재귀적으로 구현됩니다. 재귀 함수는 자기 자신을 호출하는 함수로, 여기서는 모든 가능한 벽의 조합을 찾는 데 사용됩니다. 파이썬에서 재귀를 사용할 때는 재귀 깊이에 주의해야 합니다. 이는 'sys.setrecursionlimit()' 으로 조절할 수 있습니다.

 

- 너비우선탐색(BFS) 와 큐 - 

• BFS 구현에서는 'collections' 모듈의 'deque'을 사용하여 큐를 구현합니다. 큐는 선입선출(FIFO) 구조로, 바이러스가 각 영역으로 퍼져나가는 순서를 효율적으로 관리하는 데 적합합니다.

 

- 리스트 컴프리헨션(List comprehension) -

• 파이썬의 리스트 컴프리헨션은 초기 데이터 구조를 간결하게 생성하는 데 유용합니다. 예를 들어, 'graph' 또는 'empty_space' 배열을 초기화할 때, 사용됩니다.