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

---

1. 조합 라이브러리 코드

import copy
from collections import deque
from itertools import combinations



def bfs():
    global answer
    cnt = 0
    graph = copy.deepcopy(og_graph)
    q = deque()
    for i in g:
        x, y = pos[i][0], pos[i][1]
        graph[x][y] = 'g'
        q.append((x, y))
    for i in r:
        x, y = pos[i][0], pos[i][1]
        graph[x][y] = 'r'
        q.append((x, y))

    while q:
        new = set() # 현재 시간초에 추가된 장소 집합
        for _ in range(len(q)): # 현재 시간초에 추가될 장소
            x, y = q.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if 0 <= nx < N and 0 <= ny < M:
                    if graph[nx][ny] == 1 or graph[nx][ny] == 2:
                        if graph[x][y] == 'f':
                            continue
                        graph[nx][ny] = graph[x][y]
                        q.append((nx, ny))
                        new.add((nx, ny))
                    elif graph[nx][ny] == 'r' and graph[x][y] == 'g':
                        if (nx, ny) in new or (x, y) in new:
                            graph[nx][ny] = 'f'
                            cnt += 1
                    elif graph[nx][ny] == 'g' and graph[x][y] == 'r':
                        if (nx, ny) in new or (x, y) in new:
                            graph[nx][ny] = 'f'
                            cnt += 1
    answer = max(answer, cnt)


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N, M, G, R = map(int, input().split())
og_graph = [list(map(int, input().split())) for _ in range(N)]
answer = -1

pos = []
for i in range(N):
    for j in range(M):
        if og_graph[i][j] == 2:
            pos.append((i, j))

# 땅 고르기
for i in list(combinations(list(range(len(pos))), G+R)):
    for j in list(combinations(i, G)):
        g = j
        r = tuple(set(i)-set(j))
        bfs()
print(answer)

2. DFS 사용 코드

import copy
from collections import deque
from itertools import combinations



def bfs(lst):
    global answer
    cnt = 0
    graph = copy.deepcopy(og_graph)
    q = deque()
    for i in range(len(pos)):
        x, y = pos[i]
        if lst[i] == 'r':
            graph[x][y] = 'r'
            q.append((x, y))
        elif lst[i] == 'g':
            graph[x][y] = 'g'
            q.append((x, y))

    while q:
        new = set() # 현재 시간초에 추가된 장소 집합
        for _ in range(len(q)): # 현재 시간초에 추가될 장소
            x, y = q.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if 0 <= nx < N and 0 <= ny < M:
                    if graph[nx][ny] == 1 or graph[nx][ny] == 2:
                        if graph[x][y] == 'f':  # 'r' 또는 'g' 상태일 때 큐에 저장된 경우
                            continue
                        graph[nx][ny] = graph[x][y]
                        q.append((nx, ny))
                        new.add((nx, ny))
                    elif graph[nx][ny] == 'r' and graph[x][y] == 'g':
                        if (nx, ny) in new or (x, y) in new:
                            graph[nx][ny] = 'f'
                            cnt += 1
                    elif graph[nx][ny] == 'g' and graph[x][y] == 'r':
                        if (nx, ny) in new or (x, y) in new:
                            graph[nx][ny] = 'f'
                            cnt += 1
    answer = max(answer, cnt)



def dfs(idx, rcnt, gcnt, path):
    if idx == len(pos):
        if rcnt == R and gcnt == G:
            bfs(path)
        return

    dfs(idx+1, rcnt+1, gcnt, path+['r'])  # R
    dfs(idx+1, rcnt, gcnt+1, path+['g'])  # G
    dfs(idx+1, rcnt, gcnt, path+['x'])  # x


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N, M, G, R = map(int, input().split())
og_graph = [list(map(int, input().split())) for _ in range(N)]
answer = -1

pos = []
for i in range(N):
    for j in range(M):
        if og_graph[i][j] == 2:
            pos.append((i, j))
dfs(0, 0, 0, [])
print(answer)

---

3. 후기

배양액이 설치될 수 있는 장소는 10개 이상으로 주어지지 않는다. 조합을 사용하기에 충분한 경우의 수이므로 조합을 사용했다.

그리고 R,G 가 설치될 장소를 구한다음에는 BFS를 통해 모든 경우를 시뮬레이션으로 돌린 후 갱신된 최대값을 출력한다

현재 시간초에 대한 구분은for _ in range(len(q))를 사용하여 새롭게 추가된 큐를 제외한 기존의 큐 길이만큼만 탐색함으로서 가능하다.