[python] 백준 14502 - 연구소

출처 : 백준, https://www.acmicpc.net/problem/14502

14502번: 연구소

# 벽을 3개 세울 수 있다.
# 바이러스는 상하좌우로 퍼져나간다
# 바이러스가 있는 칸은 연구소 내에 2개 이상 9개 이하이다.

# 안전영역의 최댓값을 구하여라

 

 

먼저, 생각해야 할 부분

 

1. 어떻게 해야 벽을 세울 칸을 효율적으로 선택할 수 있을지 고민해보자.

     아마.....없을 것이다. 벽을 세울 칸을 효율적으로 선택할 수 없다면...다 해봐야지 어쩌겠니...

 

2. 그렇다면 안전 영역의 개수를 어떻게 구할 수 있을까?

    VIRUS는 상하좌우로 퍼져나간다.

    어째 익숙하다. BFS, DFS이다.

---

 

반복문 BFS 풀이

반복문과 deque를 이용한 BFS 풀이이다.

from collections import deque
from copy import deepcopy

EMPTY = 0
WALL = 1
VIRUS = 2

def calcSafeAreaBFS(lab, virus_list, total_empty, new_wall):
    temp_total_empty = total_empty - 3
    temp_lab = deepcopy(lab)
    temp_virus_list = deepcopy(virus_list)

    for wr, wc in new_wall: # 벽 세우기
        temp_lab[wr][wc] = WALL

    # 바이러스의 좌표들을 queue에 넣는다.
    # 좌표 하나를 꺼내와서 상하좌우를 체크한다
    # 체크한 칸 중 EMPTY 칸이 있으면 VIRUS로 바꾸고 큐에 넣는다.
    # WALL이나 VIRUS라면 PASS
    # EMPTY를 VIRUS로 바꿀 때마다 total_empty - 1
    # queue가 빌 때까지 계속한다.

    check_dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while len(temp_virus_list) > 0:
        vr, vc = temp_virus_list.popleft()

        for dr, dc in check_dir:
            nr, nc = vr + dr, vc + dc

            # nr, nc가 범위를 벗어나면 pass
            if not 0 <= nr < n or not 0 <= nc < m:
                continue

            # EMPTY인지 체크
            if temp_lab[nr][nc] == EMPTY:
                temp_lab[nr][nc] = VIRUS  # EMPTY라면, VIRUS로 변경
                temp_total_empty -= 1  # EMPTY칸 감염 시마다 -1

                # queue에 새 좌표 추가
                temp_virus_list.append((nr, nc))

    return temp_total_empty

def solution(n, m, lab):
    virus_list = deque()
    empty_list = list()
    total_empty = 0

    # EMPTY의 모든 좌료를 구해서 성분이 3개인 조합을 만든다.

    for i in range(n):
        for j in range(m):
            if lab[i][j] == EMPTY:
                empty_list.append((i, j))
                total_empty += 1
            elif lab[i][j] == VIRUS:
                virus_list.append((i, j))

    combi_list = combination(empty_list, 3)

    # 각 MAP에 대해서 안전 영역을 구해 최댓값을 구한다.

    max_empty = -1

    # 벽을 세운 조합별로 BFS를 돌린다.
    for combi in combi_list:
        #최대 안전 영역 개수 업데이트
        max_empty = max(max_empty, calcSafeAreaBFS(lab, virus_list, total_empty, combi))

    return max_empty

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

print(solution(n, m, lab))

 

재귀 DFS 풀이 - 1

 

위 풀이에서 calcSafeAreaBFS 함수 대신 calcSafeAreaDFS와 calcPlusVirusAreaDFS 함수를 사용한 풀이이다.

solution에서는 calcSafeAreaDFS를 호출하고,

calcSafeAreaDFS가 실제 재귀 함수인 calcPlusVirusAreaDFS를 호출한다.

 

이 풀이는 칸이 EMPTY인지 판단한 후에 재귀함수를 호출하는 풀이이다.

 

def calcPlusVirusAreaDFS(lab, room): #추가적으로 전파된 방의 개수를 구하는 함수
    n = len(lab)
    m = len(lab[0])

    r, c = room

    # 방을 VIRUS로 바꾼다.
    lab[r][c] = VIRUS

    check_dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    changeVirus = 0

    # 상하좌우를 조사 후 상하좌우로부터 virus로 바뀐 칸을 누적한다.
    for dr, dc in check_dir:
        nr, nc = r + dr, c + dc

        if not 0 <= nr < n or not 0 <= nc < m:  # 범위 밖이면 PASS
            continue

        if lab[nr][nc] != EMPTY: # EMPTY가 아니면 PASS
            continue

        # EMPTY인 칸을 넣음
        changeVirus += calcPlusVirusAreaDFS(lab, (nr, nc))

    # 바이러스로 바뀐 칸들에 나 자신을 더해 return한다.
    return changeVirus + 1
    
def calcSafeAreaDFS(lab, virus_list, total_empty, new_wall): #재귀 helper 함수
    # calcPlusVirusAreaDFS에서 무조건 +1을 하므로 시작 시 VIRUS인 칸들의 개수를 빼줘야함.
    temp_total_empty = total_empty - 3 + len(virus_list)
    temp_lab = deepcopy(lab)

    for wr, wc in new_wall: # 벽 세우기
        temp_lab[wr][wc] = WALL

    # 바이러스가 있는 칸으로부터 조사를 시작한다
    for vr, vc in virus_list:
        temp_total_empty -= calcPlusVirusAreaDFS(temp_lab, (vr, vc))

    return temp_total_empty

 

재귀 DFS 풀이 - 2

 

이 풀이는 일단 주위 칸에 대해 재귀 함수 호출 후에 호출된 함수 내에서 칸이 EMPTY인지 판단하는 풀이이다.

주위 모든 칸에 대해서 일단 재귀함수를 호출하고 보기 때문에 재귀 DFS - 1 풀이보다 시간이 조금 더 걸린다.

 

def calcPlusVirusAreaDFS(lab, room):
    n = len(lab)
    m = len(lab[0])

    r, c = room

    if not 0 <= r < n or not 0 <= c < m:# 범위 밖이면 return
        return 0

    if lab[r][c] != EMPTY:# EMPTY가 아니면 return
        return 0

    # EMPTY라면 VIRUS로 바꾼다.
    lab[r][c] = VIRUS

    check_dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    changeVirus = 0

    # 상하좌우를 조사 후 상하좌우로부터 virus로 바뀐 칸을 누적한다.
    for dr, dc in check_dir:
        nr, nc = r + dr, c + dc

        changeVirus += calcPlusVirusAreaDFS(lab, (nr, nc)) # 상하좌우 중 칸을 호출

    # 바이러스로 바뀐 칸들에 나 자신을 더해 return한다.
    return changeVirus + 1

def calcSafeAreaDFS(lab, virus_list, total_empty, new_wall):
    temp_total_empty = total_empty - 3
    temp_lab = deepcopy(lab)

    for wr, wc in new_wall: # 벽 세우기
        temp_lab[wr][wc] = WALL

    check_dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    # 바이러스가 있는 칸의 상하좌우를 조사한다.
    for vr, vc in virus_list:
        for dr, dc in check_dir:
            nr, nc = vr + dr, vc + dc

            temp_total_empty -= calcPlusVirusAreaDFS(temp_lab, (nr, nc))

    return temp_total_empty

---

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들