[16번] 연구소

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

14502번: 연구소

연구소: 바이러스 전파 후 안전 영역의 최대 갯수

 

• 탐색방향: 상하좌우
• 탐색조건: MAP == 0
• 탐색결과: MAP = 2 (바이러스 영역으로 변경)
• 출발점: 바이러스 위치들
• 알고리즘 선택: 완전탐색 => BFS, DFS

 

import itertools
import collections

N, M = map(int, input().split())
MAP = []
viruses = []
emptys = []
for r in range(N):
    MAP.append(list(map(int, input().split())))
    for c in range(M):
        if MAP[r][c] == 2:
            viruses.append((r, c))
        elif MAP[r][c] == 0:
            emptys.append((r, c))

candidates = itertools.combinations(emptys, 3)  # 빈 공간 3개를 선택

max_safe = 0
temp = [[0] * M for _ in range(N)]
for candi in candidates:
    # 벽 3개 설치
    for r in range(N):
        for c in range(M):
            temp[r][c] = MAP[r][c]  # 탐색결과 MAP이 변경되므로 temp 생성
            
    for r, c in candi:
        temp[r][c] = 1

    # 바이러스 전파 (BFS)
    qu = collections.deque(viruses)
    while qu:
        x, y = qu.popleft()
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M:
                if temp[nx][ny] == 0:
                    temp[nx][ny] = 2
                    qu.append((nx, ny))

    # 안전영역 계산
    safe = 0
    for r in range(N):
        for c in range(M):
            if temp[r][c] == 0:
                safe += 1
    max_safe = max(max_safe, safe)

print(max_safe)  # 2

 

itertools 사용 대신에 직접 dfs 로 구현할수도 있지만...  => 조합이 아니라 순열이므로 느리다 (PyPY3)

 

import collections

N, M = map(int, input().split())
MAP = []
viruses = []
for r in range(N):
    MAP.append(list(map(int, input().split())))
    for c in range(M):
        if MAP[r][c] == 2:
            viruses.append((r, c))


def select_emptys(repeat):
    global max_safe
    if repeat == 0:
        for r in range(N):
            for c in range(M):
                temp[r][c] = MAP[r][c]  # 탐색결과 MAP이 변경되므로 temp 생성

        # 바이러스 전파 (BFS)
        qu = collections.deque(viruses)
        while qu:
            x, y = qu.popleft()
            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < N and 0 <= ny < M:
                    if temp[nx][ny] == 0:
                        temp[nx][ny] = 2
                        qu.append((nx, ny))

        # 안전영역 계산
        safe = 0
        for r in range(N):
            for c in range(M):
                if temp[r][c] == 0:
                    safe += 1
        max_safe = max(max_safe, safe)
        return

    for r in range(N):
        for c in range(M):
            if MAP[r][c] == 0:
                MAP[r][c] = 1
                select_emptys(repeat - 1)
                MAP[r][c] = 0


max_safe = 0
temp = [[0] * M for _ in range(N)]
select_emptys(3)  # 3번 선택
print(max_safe)   # 2

 

3 3
0 0 2
1 1 0
1 0 0