[DFS/BFS] 연구소

문제링크

https://www.acmicpc.net/problem/14502

• 문제 이해하는 데도 상당히 오랜 시간이 걸린 문제이다
• 0 갯수를 최대화 할 수 있도록 1을 3개 세워야하는 문제이다
• 2가 탐색 방식으로 확장해나가는 구조라 생각하면 좀 더 쉽게 생각이 가능하다
  • 1이 나올때 까지 0을 2로 바꿔버린다

 

해설

• 이 문제야 말로 컴퓨터가 인간보다 잘 푸는 유형의 대표적인 예라고 생각한다
• 전체 조합을 모두 고려해야하는 상황에서는 dfs를 먼저 생각할 줄 알아야 한다

 

 풀이과정

1. 3개의 벽을 골라 벽을 설치한다
2. 각 바이러스가 사방으로 퍼지는 것을 DFS/BFS로 계산하여 안전 영역을 구한다

 

전체 코드

 

dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

result = 0

def is_valid_coord(x, y):
    return 0 <= x < n and 0 <= y < m

# 깊이 우선 탐색(DFS)를 이용해 각 바이러스가 사방으로 퍼지도록 하기
def virus(x, y):
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if is_valid_coord(nx, ny):
            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] = graph[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 graph[i][j] == 0:
                graph[i][j] = 1
                count += 1
                dfs(count)
                graph[i][j] = 0
                count -= 1

dfs(0)
print(result)

 

다른 풀이

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

def bfs():
    queue = deque()
    tmp_graph = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if tmp_graph[i][j] == 2:
                queue.append((i, j))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if tmp_graph[nx][ny] == 0:
                tmp_graph[nx][ny] = 2
                queue.append((nx, ny))

    global answer
    cnt = 0
    for i in range(n):
        cnt += tmp_graph[i].count(0)
    answer = max(answer, cnt)


def makeWall(cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                makeWall(cnt+1)
                graph[i][j] = 0

n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

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

answer = 0
makeWall(0)
print(answer)

 

총평/느낀점

• 이제 어느정도는 DFS/BFS로 풀어야하는 유형을 구분할 수 있게 된 것 같다.
• 너무 어렵다..

 

출처

• 이것이 코딩테스트다