[BFS/DFS] 연구소 (python)

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

14502번: 연구소

 

이 문제는 가장 많은 안전 영역이 남아있는 벽 3개의 위치를 구해야하는데,

결론적으로는 벽 3개의 모든 조합의 경우의 수를 다 시도해봐야 한다!

 

그리고 바이러스가 퍼뜨릴 수 있을 때까지 계속 퍼뜨려야 해서,

BFS/DFS 두가지로 다 풀 수 있다! (BFS가 조금 더 빠름)

 

Point : 가장 많은 안전 영역이 남아있는 벽 3개의 위치 구하기

• 벽 3개의 위치는 조합으로 모든 경우의 수를 시도해보기
• 바이러스를 (빈 공간이 있을 경우) 계속 퍼뜨리기 -> BFS/DFS

 

 

1. BFS + 조합

최초의 바이러스 위치는 배열로 저장하고,

BFS 함수 내부에서는 큐를 활용하여 바이러스들을 관리해준다!

(퍼뜨려진 바이러스들도 계속 추가해주고, 그 바이러스들도 퍼뜨린다)

from itertools import combinations, count
import copy
from collections import deque
n, m = map(int, input().split())
graph = []
blank = []
virus = []
for i in range(n):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(m):
        if graph[i][j] == 0:
            blank.append((i, j))
        elif graph[i][j] == 2:
            virus.append((i, j))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(tmp):
    q = deque(virus)
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if tmp[nx][ny] == 0:
                    tmp[nx][ny] = 2
                    q.append((nx, ny))

    score = 0
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 0:
                score += 1

    return score

result = 0
for case in combinations(blank, 3):
    tmp = copy.deepcopy(graph)
    for x, y in case:
        tmp[x][y] = 1
    result = max(result, bfs(tmp))

print(result)

 

 

2. DFS + 조합

모든 위치에서 DFS 함수를 시작해주고,

DFS 함수는 재귀적으로 반복해준다.

from itertools import combinations, count
import copy
n, m = map(int, input().split())
graph = []
blank = []
for i in range(n):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(m):
        if graph[i][j] == 0:
            blank.append((i, j))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def dfs(x, y, tmp):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if tmp[nx][ny] == 0:
                tmp[nx][ny] = 2
                dfs(nx, ny, tmp)


def get_score(tmp):
    count = 0
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 0:
                count += 1
    return count


result = 0
for case in combinations(blank, 3):
    tmp = copy.deepcopy(graph)
    for x, y in case:
        tmp[x][y] = 1
    for i in range(n):
        for j in range(m):
            if tmp[i][j] == 2:
                dfs(i, j, tmp)
    result = max(result, get_score(tmp))

print(result)