[백준 - 14502] 연구소

문제

문제링크

연구소 크기는 N X M ( 3 <= N, M <= 8)
빈칸 0, 벽 1, 바이러스 2 로 표현하고 벽을 추가로 3개를 세워서 바이러스의 유출을 최소화 하고싶다. 최소화 시킨 경우의 안전지대 크기를 출력하라.

문제 풀이

전체 경우에 탐색을 진행해도 8*8C3 에 해당한다.
그러므로 전체 경우에 대해 하나씩 DFS/BFS로 가능하지 않을까? 라고 생각했다.

from itertools import combinations
import copy

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

# 연구소는 빈칸, 벽, 바이러스가 존재
blank = []
wall = []
virus = []
array = []
for r in range(n):
    temp = list(map(int, input().split()))
    for c, t in enumerate(temp):
        if t == 0: # 빈칸인 경우
            blank.append((r, c))
        elif t == 1: # 벽인 경우
            wall.append((r, c))
        else :
            virus.append((r,c))
    array.append(temp)

def spread(location, t_array):
    x, y = location
    t_array[x][y] = 2

    # 4 방면으로 뿌리기
    if 0 < x and t_array[x-1][y] == 0:
        spread((x-1, y), t_array)
    if x < n - 1 and t_array[x+1][y] == 0 :
        spread((x+1, y), t_array)
    if 0 < y and t_array[x][y-1] == 0:
        spread((x, y-1), t_array)
    if y < m - 1 and t_array[x][y+1] == 0:
        spread((x, y+1), t_array)

answer = 0
for selected in list(combinations(blank, 3)):
    # 3가지 점을 선택해서 벽을 세운다.
    t_array = copy.deepcopy(array)
    for (x, y) in selected:
        t_array[x][y] = 1
    # virus를 퍼트린다.
    for location in virus:
        spread(location, t_array)
    # 0으로 안전지대만을 체크한다.
    score = 0
    for i in range(n):
        for j in range(m):
            if t_array[i][j] == 0:
                score += 1

    answer = max(answer, score)
print(answer)

개선할 점

바이러스 퍼트리는 과정인 BFS에서 문제가 많았다. 결국 문제는 조건문의 조건이 하나가 잘못되어있었다. 실수하지말자! 하지만, 이제 문제를 파악하고 활용하는 눈을 조금씩 키워지는 것 같다.

아래는 DFS를 활용한 풀이방법이다.

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 = 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로 아래가 BFS로 풀이한 결과이다. 예상하기에는 근처에 퍼트려나가는 방식이라 BFS가 깊게 빠지지 않는 걸로 보인다. 앞으로도 문제를 잘 파악하고 접근하자!

해당 문서는 '이것이 코딩 테스트다 with 파이썬 - 나동빈 저'를 공부하고 정리한 글입니다.