Garden

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

Algorithm

1. 초록색 배양액과 빨간색 배양액을 뿌릴 수 있는 모든 조합을 구한다.
2. 각각의 경우에 대해 배양액을 퍼뜨리며 피울 수 있는 꽃을 센다.
3. 피울 수 있는 꽃의 최대 개수를 출력한다.
   
   

for comb in combinations(range(len(spot)), G + R):
    comb = set(comb)

    for g in combinations(comb, G):
        g = set(g)
        r = comb - g

        MAX = max(MAX, spread())

Key Point

• 좌표들의 조합은 combinations(range(len(spot)) 와 같이 List 인덱스 조합으로 구할 수 있다.
• set을 활용하여 조합을 구하는 것은 효율적이다.

def spread():
    tboard = copy.deepcopy(board)
    count = 0

    Gq = deque([spot[index] for index in g])
    Rq = deque([spot[index] for index in r])

    for x, y in Gq:
        tboard[x][y] = 0
    for x, y in Rq:
        tboard[x][y] = 0

    while Gq and Rq:
        for _ in range(len(Gq)):
            x, y = Gq.popleft()
            if tboard[x][y] == 'F':
                continue

            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if 0 <= nx < N and 0 <= ny < M and tboard[nx][ny] == 1:
                    tboard[nx][ny] = 'G'
                    Gq.append((nx, ny))

        for _ in range(len(Rq)):
            x, y = Rq.popleft()
            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if 0 <= nx < N and 0 <= ny < M:
                    if tboard[nx][ny] == 'G':
                        tboard[nx][ny] = 'F' # flower
                        count += 1
                    elif tboard[nx][ny] == 1:
                        tboard[nx][ny] = 0
                        Rq.append((nx, ny))

        for x, y in Gq:
            if tboard[x][y] == 'G': # expired
                tboard[x][y] = 0

    return count

Key Point

• 배양액이 만나 꽃이 피면 그 지점에서는 더 이상 탐색하지 않는다.
• 빨간색 배양액이 초록색 배양액을 만나지 못했다면 만료시킨다.
• 현재 위치에 꽃이 피어있다면 CONTINUE.