[BOJ 14502] 연구소

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

문제 접근

최종 목표: 안전 영역의 최대 크기를 출력

위와 같은 문제는 어떻게 쉬운 문제로 쪼갤 수 있을까?🤔

문제 쪼개기

1.벽 3개 임의로 배치
2. 바이러스가 퍼지는 것을 BFS로 구현
3. 1과 2를 수행한 후에 지도 상에 존재하는 0의 개수 세기
4. 1~3 반복해서 0이 가장 많은 결과(안전 영역의 최대 크기) 출력

우선 이렇게 4개의 작은 문제로 쪼개서 생각해보았다.
모든 경우를 시도하여 안전 영역의 최대 크기를 찾아보자

문제 해결 아이디어

모든 경우의 수 계산

다만, 구현하기 까다로워서 연습이 필요하다.

코드

from collections import deque

n, m = map(int, input().split())
data = [list(map(int, input().split())) for i in range(n)]
temps = [[0] * m for _ in range(n)]

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

answer = 0

def walls_dfs(num_walls):
    global answer
    # 벽 3개 배치 
    if num_walls == 3:
        for i in range(n):
            for j in range(m):
                temps[i][j] = data[i][j]

        # 바이러스 전파
        for i in range(n):
            for j in range(m):
                if temps[i][j] == 2:
                    virus_bfs(i, j)
        # 안전영역 계산
        answer = max(answer,  get_score())
        return

    # 빈 공간에 울타리 설치
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                num_walls += 1
                walls_dfs(num_walls)
                data[i][j] = 0
                num_walls -= 1

def virus_bfs(x, y):
    queue = deque([(x, y)])
    # 현재노드 방문처리
    temps[x][y] = 2
    while queue:
        x, y = queue.popleft()
        # 인접 노드 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위에 해당하는 경우
            if (0 <= nx < n) and (0 <= ny < m):
                # 방문하지 않은 경우
                if temps[nx][ny] == 0:
                    temps[nx][ny] = 2
                    queue.append((nx, ny))

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

walls_dfs(0)
print(answer)