[백준 18809] Gaaaaaaaaaarden - Python

문제 보기

[사용한 알고리즘]

브루트 포스, 조합

 

[문제 접근]

배양액을 놓을 수 있는 공간에 초록색 배양액과 빨간색 배양액을 놓는 모든 경우에 대해서 시뮬레이션하였습니다. 배양액을 놓고 시간에 따라 퍼지는 동작을 실행해야만 꽃의 개수를 파악할 수 있기 때문에 모든 경우의 수를 확인하였습니다.

 

[알고리즘]

1. 배양액을 놓을 수 있는 공간 중 초록색 배양액을 놓을 공간을 구합니다.

2. 배양액을 놓을 수 있는 공간 중 빨간색 배양액을 놓을 공간을 구합니다.

3. 1, 2 과정을 거친 후 시간에 따라 배양액이 퍼지는 과정을 시뮬레이션합니다.

4. 1~3 과정을 모든 경우의 수에 대해 적용해보고 피울 수 있는 꽃의 최대 개수를 출력합니다.

 

[코드]

from itertools import combinations
from collections import deque
import sys
import copy

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


def bfs(array, selected, green):
    cnt = 0
    green_q = deque()
    red_q = deque()

    for row, col in selected:
        if [row, col] in green:
            green_q.append([row, col])  # 초록색 배양액
            array[row][col] = 3
        else:
            red_q.append([row, col])  # 빨간색 배양액
            array[row][col] = 4

    while green_q:  # 초록색 배양액이 빌때까지
        green_temp = set()
        red_temp = set()
        while green_q:
            x, y = green_q.popleft()
            array[x][y] = 3
            for i in range(4):
                new_x, new_y = x + dx[i], y + dy[i]
                if 0 <= new_x < n and 0 <= new_y < m:
                    if array[new_x][new_y] == 1 or array[new_x][new_y] == 2:
                        green_temp.add((new_x, new_y))
        while red_q:
            x, y = red_q.popleft()
            array[x][y] = 4
            for i in range(4):
                new_x, new_y = x + dx[i], y + dy[i]
                if 0 <= new_x < n and 0 <= new_y < m:
                    if array[new_x][new_y] == 1 or array[new_x][new_y] == 2:
                        red_temp.add((new_x, new_y))

        inter = green_temp & red_temp
        green_temp = green_temp - inter
        red_temp = red_temp - inter
        for row, col in inter:
            array[row][col] = 5
            cnt += 1
        for row, col in green_temp:
            array[row][col] = 3
        for row, col in red_temp:
            array[row][col] = 4
        green_q.extend(green_temp)
        red_q.extend(red_temp)

    return cnt


if __name__ == "__main__":
    n, m, g, r = map(int, sys.stdin.readline().split())
    maps = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    # 배양액을 뿌릴 수 있는 위치, 뿌릴 수 없는 위치 탐색
    location = []
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 2:
                location.append([i, j])

    answer = 0
    for selected in list(combinations(location, g + r)):
        # selected를 green과 red로 나누기
        for green in list(combinations(selected, g)):
            copy_maps = copy.deepcopy(maps)
            answer = max(answer, bfs(copy_maps, selected, green))

    # 출력
    print(answer)