[백준] 18809 Gaaaaaaaaaarden, python

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

 

 

 

 

 

배양액을 뿌릴 수 있는 땅에 빨간색, 초록색을 뿌리는 모든 케이스를 구한다.

각 케이스마다 bfs를 통해 꽃의 개수를 구하고, 최댓값을 구하면 된다.

 

 

 

먼저 배양액을 뿌릴 수 있는 땅의 좌표를 배열에 저장한다.

배양액을 뿌릴 수 있는 땅 중에서 배양액을 뿌릴 땅을 선택한다.

위에서 선택된 땅에서 초록색을 뿌릴 땅을 선택한다. 나머지는 빨간색을 뿌리면된다.

 

예를들면 배양액을 5개의 땅에 뿌릴 수 있다하고 초록색 배양액 2개 , 빨간색 배양액 1개를 뿌린다 하면, 먼저 5개중 3개를 고른다.

그리고 고른 3개중에서 2개는 초록색, 1개는 빨간색을 뿌리면된다.

combination을 사용해서 각각의 경우의 수를 구해주었다.

 

 

 

배양액들이 동일한 시간에 도달하는지를 체크해야 한다. bfs 탐색을 할때 초기 큐에 있는 값은 모두 같은 시간이므로 큐의 길이만큼 탐색을 하게되면 현재 시간을 전부 처리한 후 다음 시간으로 넘어갈 수 있다. 

 

먼저 초록색이 퍼질 다음 좌표의 후보를 저장할 set을 생성한다.

초록색에서 1번 퍼트린다. 배양액이 새로 퍼진 좌표의 후보를 set에 담는다.

빨간색에서 1번 퍼트리고, 만약 빨간색이 새로 퍼진 좌표가 후보에 있다면, 두 배양액이 만난 것이므로 꽃의 개수를  +1 해준다.

꽃이 피어난 자리에서는 퍼트릴 수 없으므로 후보에서 제외해주게 되면, 후보에 남은 좌표는 초록색이 최종적으로 퍼트려진 좌표가 된다.

이제 초록색이 퍼진 좌표, 빨간색이 퍼진 좌표를 큐에 넣고 더 이상 퍼트릴수 없을때 까지 반복해주면된다.

 

 

 

 

import sys
from itertools import*
from collections import*
input = sys.stdin.readline

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

# 배양액을 뿌릴 수 있는 땅의 좌표를 저장
pos = []
for i in range(n):
    for j in range(m):
        if garden[i][j]==2:
            pos.append((i,j))

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

def spread(green,red):
    g = [x[:] for x in garden]
    visited = [[0]*m for _ in range(n)]

    # 처음 배양액을 뿌린 좌표에 방문체크
    # 초록색이 뿌려졌다면 1, 빨간색이 뿌려졌다면 2
    for i,j in green:
        visited[i][j] = 1
    for i,j in red:
        visited[i][j] = 2

    q_red = deque(red)
    q_green =deque(green)
    res = 0

    while q_green and q_red:
        # 초록색이 새로 퍼트려지는 좌표의 후보를 저장
        s = set()
        qlen = len(q_green)
        for _ in range(qlen):
            cx,cy = q_green.popleft()

            for i in range(4):
                nx,ny = cx+dx[i],cy+dy[i]
                if 0<=nx<n and 0<=ny<m:
                    if (g[nx][ny] == 1 or g[nx][ny] == 2) and visited[nx][ny]==0:
                        visited[nx][ny] = 1
                        s.add((nx,ny))
        
        qlen = len(q_red)
        for _ in range(qlen):
            cx,cy = q_red.popleft()

            for i in range(4):
                nx,ny = cx+dx[i],cy+dy[i]
                if 0<=nx<n and 0<=ny<m:
                    if g[nx][ny] == 1 or g[nx][ny] == 2:
                        if visited[nx][ny]==0:
                            visited[nx][ny] = 2
                            q_red.append((nx,ny))
                        # 만약 해당좌표에 초록색이 뿌려졌다면
                        elif visited[nx][ny]==1:
                            if (nx,ny) in s:
                                # 후보에서 제거하고 꽃의 개수를 1더해준다
                                s.remove((nx,ny))
                                res += 1

        # 남은 후보들은 초록색 배양액이 다음으로 퍼질 좌표이다
        for pos in s:
            q_green.append(pos)
    
    return res

answer = 0

# 배양액이 뿌려질 수 있는 땅에 실제 배양액이 뿌려질 좌표 케이스를 구함
for comb in combinations(pos,g+r):
    # 실제 뿌려진 땅에서 빨강색이 뿌려질 좌표를 구함
    for red in combinations(comb,r):
        green = list(green)
        red = [x for x in comb if x not in red]
        answer = max(answer,spread(green,red))

print(answer)