[BOJ] 18809. Gaaaaaaaaaarden (🥇, 구현/시뮬레이션/BFS)

🔗

풀이

• 배양액을 뿌릴 수 있는 곳에 모든 배양액을 뿌린다
• 배양액은 각각 1칸씩 상하좌우로 퍼질 수 있다
• 서로 다른 색의 배양액이 동시에 도착하는 칸은 꽃이 핀다
• 꽃이 핀 칸은 더 이상 퍼지지 않는다
• 호수에는 배양액이 퍼질 수 없다

배양액을 뿌릴 수 있는 칸 K(<=10)칸 중에서 (R+G)칸만 골라내는 중복조합이다. 최대 10칸까지 존재할 수 있고 R과 G는 각각 최대 5칸이므로 10!/(5!x5!) = 252가지가 최대로 존재할 수 있다. 배양액을 뿌릴 수 있는 모든 경우의 수에 대해 구하고 각각에 대해 각 배양액이 퍼졌을 때의 결과에 대해 구하면 된다.

같은 시간에 같은 칸에 도착한 경우에 대해 구해야 하므로 너비우선탐색을 사용한다. 초록색과 빨간색의 배양액에 대해 각각 구분해야 한다. 이때, 빈칸에 도달한다면 도달한 배양액의 바로 저장하지만, 초록색 배양액일 때 빨간색 칸이거나, 빨간색 배양액일 때 초록색 칸이라면 각 도달시간을 비교해야 한다. 도달한 시간이 동일하다면 꽃을 피우고 그렇지 않다면 그냥 지나간다.

이때 주의해야 할 점은, 만약 특정 배양액이 도달했을 땐 빈칸이었으나 뒤이어 다른 색의 배양액이 그 칸에 동시에 도달하게 되었을 때는 탐색을 위해 큐에 이미 추가된 칸이 나중에 꽃이 되어버린 경우이므로 이 칸의 탐색을 중단시켜야 한다. 예를 들어 초록색 배양액이 특정 칸에 도달했을 때는 비어있어서 초록색 칸으로 물들이고 뒤이은 탐색을 위해 큐에 추가까지 했는데 뒤이어 빨간색 배양액이 같은 시간이 도달해버리면 큐에 추가했던 그 칸은 꽃이 되었기 때문에 큐에서 꺼냈을 때 탐색을 하면 안 되는 것이다. 이걸 몰라서 엄청 헤맸다.

참고로 Python3로는 시간초과가 발생한다.

# Gaaaaaaaaaarden

# 배양액을 뿌릴 수 있는 땅 찾기
def find_land(arr):
    queue = []
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 2:
                queue.append((i, j))
    return queue

# 배양액을 뿌릴 수 있는 중복조합 구하기
def dfs(i, k, tmp, lst, comb):
    if len(tmp) == k:
        comb.append(tmp[:])
        return comb
    
    for j in range(i, len(lst)):
        if lst[j] not in tmp:
            tmp.append(lst[j])
            comb = dfs(j+1, k, tmp, lst, [row[:] for row in comb])
            tmp.remove(lst[j])
    return comb

# 배양액 퍼뜨리기
def bfs(green, red, medium_land):
    arr = [[[0, 0] for _ in range(m)] for _ in range(n)]
    queue = []
    for i in green:
        gx, gy = medium_land[i]
        arr[gx][gy] = [GREEN, 0]
        queue.append((gx, gy))
    for j in red:
        rx, ry = medium_land[j]
        arr[rx][ry] = [RED, 0]
        queue.append((rx, ry))

    flowers = 0
    while queue:
        x, y = queue.pop(0)

        # 현재 탐색하려는 칸이 이미 꽃이라면 탐색 불가
        if arr[x][y][0] == FLOWER:
            continue
        count = arr[x][y][1]
        for nx, ny in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
            # 범위에 속하지 않거나 호수이거나 같은 색의 배양액이거나 꽃인 경우
            if not(-1<nx<n and -1<ny<m) or land[nx][ny] == 0 or arr[nx][ny][0] in (arr[x][y][0], 3):
                continue
                
            if arr[x][y][0] == GREEN:
                if arr[nx][ny][0] == RED and arr[nx][ny][1] == count+1:
                    arr[nx][ny][0] = FLOWER
                    flowers += 1
            elif arr[x][y][0] == RED:
                if arr[nx][ny][0] == GREEN and arr[nx][ny][1] == count+1:
                    arr[nx][ny][0] = FLOWER
                    flowers += 1
            if arr[nx][ny][0] == EMPTY:
                arr[nx][ny] = [arr[x][y][0], count+1]
                queue.append((nx, ny))

    return flowers

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

medium_land = find_land(land)
combs, lst, max_result = [], range(len(medium_land)), 0
EMPTY, GREEN, RED, FLOWER = 0, 1, 2, 3
for green in dfs(0, g, [], lst, []):
    for red in dfs(0, r, [], [row for row in lst if row not in green], []):
        max_result = max(max_result, bfs(green, red, medium_land))

print(max_result)