[Gold I] Gaaaaaaaaaarden - 18809

문제 링크

성능 요약

메모리: 213404 KB, 시간: 2392 ms

분류

구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 시뮬레이션, 너비 우선 탐색, 백트래킹

문제 설명

길고 길었던 겨울이 끝나고 BOJ 마을에도 봄이 찾아왔다. BOJ 마을에서는 꽃을 마을 소유의 정원에 피우려고 한다. 정원은 땅과 호수로 이루어져 있고 2차원 격자판 모양이다.

인건비 절감을 위해 BOJ 마을에서는 직접 사람이 씨앗을 심는 대신 초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피울 것이다. 이 때 배양액을 뿌릴 수 있는 땅은 미리 정해져있다.

배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다.

아래는 초록색 배양액 2개를 뿌렸을 때의 예시이다. 하얀색 칸은 배양액을 뿌릴 수 없는 땅을, 황토색 칸은 배양액을 뿌릴 수 있는 땅을, 하늘색 칸은 호수를 의미한다.

초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 땅에서는 두 배양액이 합쳐져서 꽃이 피어난다. 꽃이 피어난 땅에서는 배양액이 사라지기 때문에 더 이상 인접한 땅으로 배양액을 퍼트리지 않는다.

아래는 초록색 배양액 2개와 빨간색 배양액 2개를 뿌렸을 때의 예시이다.

배양액은 봄이 지나면 사용할 수 없게 되므로 주어진 모든 배양액을 남김없이 사용해야 한다. 예를 들어 초록색 배양액 2개와 빨간색 배양액 2개가 주어졌는데 초록색 배양액 1개를 땅에 뿌리지 않고, 초록색 배양액 1개와 빨간색 배양액 2개만을 사용하는 것은 불가능하다.

또한 모든 배양액은 서로 다른 곳에 뿌려져야 한다.

정원과 두 배양액의 개수가 주어져있을 때 피울 수 있는 꽃의 최대 개수를 구해보자.

입력

첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다.

그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양액을 뿌릴 수 있는 땅을 의미한다.

배양액을 뿌릴 수 있는 땅의 수는 R+G개 이상이고 10개 이하이다.

출력

첫째 줄에 피울 수 있는 꽃의 최대 개수를 출력한다.

---

문제 풀이

문제 분석

이 문제는 N행 M열의 격자 정원에서 초록색 배양액 G개와 빨간색 배양액 R개를 사용하여 피울 수 있는 꽃의 최대 개수를 찾는 문제입니다. 정원 칸은 호수(0), 배양액을 뿌릴 수 없는 땅(1), 배양액을 뿌릴 수 있는 땅(2)으로 나뉩니다. 배양액은 매 초마다 인접한 땅으로 퍼져나가며, 초록색과 빨간색 배양액이 동일한 시간에 동일한 칸에 도달하면 꽃이 피어납니다. 꽃이 피어난 칸에서는 배양액이 사라지므로 더 이상 퍼지지 않습니다. 주어진 모든 배양액(G+R개)은 남김없이 서로 다른 땅에 뿌려져야 합니다. N, M은 최대 50이고, G, R은 최대 5입니다. 특히 "배양액을 뿌릴 수 있는 땅의 수는 R+G개 이상 10개 이하"라는 제약이 중요합니다.

접근 방법

문제의 핵심 제약 사항은 '배양액을 뿌릴 수 있는 땅의 수가 최대 10개'라는 점입니다. 이는 전체 배양액 개수(G+R)도 최대 10개라는 것을 의미합니다. 이 숫자가 매우 작기 때문에, 배양액을 뿌릴 수 있는 모든 땅들 중에서 초록색 G개와 빨간색 R개를 선택하는 모든 경우의 수를 시도하는 완전 탐색 (브루트포스) 접근이 가능합니다.

각 배양액 시작 위치 조합에 대해서는 배양액이 퍼져나가고 꽃이 피는 과정을 시뮬레이션해야 합니다. 이 시뮬레이션은 최단 거리 탐색과 유사하므로 **너비 우선 탐색 (BFS)**을 사용합니다. 특히 두 종류의 배양액이 동시에 퍼져나가는 상황을 처리해야 하므로, 하나의 BFS 큐를 사용하여 두 배양액의 확산을 함께 관리하는 "동시 BFS" 방식이 적합합니다.

정리하면, 다음과 같은 단계로 문제를 해결합니다.

1. 조합(Combinations)을 이용한 시작 위치 선정: 배양액을 뿌릴 수 있는 모든 땅 중에서 G개의 초록색 배양액 시작점과 R개의 빨간색 배양액 시작점을 선택하는 모든 조합을 생성합니다.
2. BFS 시뮬레이션: 각 시작점 조합에 대해, BFS를 사용하여 배양액 확산 및 꽃 생성 과정을 시뮬레이션하고, 이때 피어나는 꽃의 개수를 계산합니다.
3. 최대값 갱신: 모든 조합에 대해 계산된 꽃의 개수 중 최댓값을 찾아 출력합니다.

구현 설명

1. 배양액을 뿌릴 수 있는 땅 목록화 및 초기화

• 입력으로 주어진 graph에서 값이 2인 칸들(배양액을 뿌릴 수 있는 땅)의 좌표를 찾아 grounds 리스트에 저장합니다.
• 이때 graph의 해당 칸 값을 1로 변경합니다. 이는 배양액이 뿌려지면 일반적인 '배양액을 뿌릴 수 있는 땅'과 동일하게 취급되어 확산이 가능하도록 하기 위함입니다.
• directions 리스트는 상하좌우 4방향 탐색에 사용될 (dx, dy) 쌍을 정의합니다.

2. 배양액 시작 위치 조합 생성

• itertools.combinations 함수를 활용하여 grounds 리스트에서 초록색 배양액 x개(G)를 뿌릴 위치들을 선택합니다.
• 초록색 위치들이 선택되면, grounds에서 선택된 초록색 위치들을 제외한 나머지 땅들을 remain 리스트에 저장합니다.
• 다시 itertools.combinations를 사용하여 remain 리스트에서 빨간색 배양액 y개(R)를 뿌릴 위치들을 선택합니다.
• 이렇게 생성된 모든 (초록색 배양액 위치 집합, 빨간색 배양액 위치 집합) 쌍에 대해 BFS 함수를 호출하여 꽃의 개수를 계산하고, max_flowers 변수에 최댓값을 저장합니다.

3. 동시 BFS 탐색 및 꽃 생성 (BFS 함수)

• BFS 함수는 두 가지 배양액의 확산 정보를 동시에 관리하기 위해 visited 2차원 배열을 [[도달 시간, 배양액 종류]] 형태로 초기화합니다.
  • 도달 시간: 배양액이 해당 칸에 도달한 시간 (0부터 시작).
  • 배양액 종류: 0 (초록), 1 (빨강), 3 (꽃이 피어 더 이상 확산되지 않음), -1 (미방문).
• deque를 BFS 큐로 사용하며, 초록색 배양액 시작점 (x, y, 0)과 빨간색 배양액 시작점 (x, y, 1)을 모두 큐에 넣고 visited 배열을 초기화합니다.
• 큐에서 (x, y, color)를 하나씩 꺼내면서 탐색을 진행합니다.
  • 꽃이 핀 칸은 건너뛰기: 만약 현재 칸 (x, y)가 이미 꽃이 피어난 칸(visited[x][y][1] == 3)이라면, 이 칸에서는 더 이상 배양액이 퍼지지 않으므로 다음 큐 요소를 처리합니다.
  • 인접 칸 탐색: 현재 칸의 상하좌우 4방향 인접 칸 (sx, sy)를 확인합니다.
    • 유효한 격자 범위 내에 있고 graph[sx][sy] == 1 (땅)인 경우에만 탐색합니다.
    • 미방문 칸: visited[sx][sy][0] == -1이라면, 해당 칸은 아직 배양액이 도달하지 않았습니다. 현재 배양액의 (도달 시간 + 1)과 color로 visited[sx][sy]를 업데이트하고 큐에 추가합니다.
    • 방문했지만 다른 종류 배양액: visited[sx][sy][1] != color이고 visited[sx][sy][1] != 3이라면, 이전에 다른 종류의 배양액이 이미 도달한 상태입니다. 이때, 두 배양액이 동일한 시간에 도달하는지 확인합니다. 즉, visited[sx][sy][0] == visited[x][y][0] + 1인지 비교합니다.
      • 조건이 충족되면 꽃이 피므로 flowers 개수를 1 증가시키고, visited[sx][sy][1]을 3으로 변경하여 이 칸에서는 더 이상 배양액이 퍼지지 않도록 합니다.

4. 결과 반환 및 최댓값 출력

• BFS 함수는 모든 배양액 확산 및 꽃 생성이 완료된 후 최종 flowers 개수를 반환합니다.
• 메인 로직은 모든 가능한 시작 위치 조합에 대해 BFS를 실행하고, 반환된 flowers 개수들 중 max_flowers의 최댓값을 갱신합니다.
• 모든 조합 탐색이 끝나면 max_flowers를 출력합니다.

⏱복잡도 분석

• 시간 복잡도:

  • 시작 위치 조합 생성: 배양액을 뿌릴 수 있는 땅의 최대 개수가 10개입니다. 이 10개 중에서 G개의 초록색 배양액 위치와 R개의 빨간색 배양액 위치를 선택하는 경우의 수는 최대 $\binom{10}{5} \times \binom{5}{5} = 252 \times 1 = 252$ 가지입니다. 이 값은 매우 작습니다.
  • BFS 함수: 각 BFS는 N*M 크기의 격자를 탐색합니다. 각 칸은 큐에 최대 한 번 추가되고, 인접한 4방향을 탐색합니다. 따라서 BFS 한 번의 시간 복잡도는 O(N*M)입니다. N, M이 최대 50이므로, O(50*50) = O(2500)입니다.
  • 총 시간 복잡도: (시작 위치 조합 경우의 수) * (BFS 시간 복잡도) = $252 \times O(N \times M)$. 최악의 경우 약 $252 \times 2500 \approx 6.3 \times 10^5$ 연산으로, 시간 제한(2초) 내에 충분히 수행 가능합니다.

• 공간 복잡도:

  • graph 배열: O(N*M)
  • visited 배열: O(N*M) (각 칸에 [도달 시간, 배양액 종류]를 저장)
  • queue: 최악의 경우 모든 칸이 큐에 들어갈 수 있으므로 O(N*M)
  • grounds 리스트: 최대 10개의 좌표를 저장하므로 O(1) (N, M에 독립적).
  • 총 공간 복잡도: O(N*M). N, M이 최대 50이므로 O(50*50) = O(2500)은 메모리 제한 내에 충분히 사용 가능합니다.

핵심 포인트

1. 제한된 시작 위치를 활용한 완전 탐색: 배양액을 뿌릴 수 있는 땅의 개수(최대 10개)가 매우 적다는 점을 파악하여, itertools.combinations로 모든 가능한 G개 초록색 및 R개 빨간색 시작 위치 조합을 생성하는 것이 이 문제 풀이의 출발점입니다.
2. 동시 BFS와 상태 관리: 두 종류의 배양액이 동시에 퍼져나가는 시뮬레이션을 위해 하나의 BFS 큐를 사용하고, 각 칸의 visited 정보를 [도달 시간, 배양액 종류] 형태로 상세하게 관리하여 꽃이 피는 조건을 정확하게 판단하는 것이 중요합니다.
3. 꽃 피는 조건 및 확산 중단: 두 배양액이 "동일한 시간"에 "동일한 칸"에 도달했을 때 꽃이 피고, 꽃이 피어난 칸(visited[x][y][1] == 3)에서는 더 이상 배양액이 퍼지지 않도록 처리하여 불필요한 탐색을 줄이고 정확한 결과를 도출하는 것이 중요합니다.

풀이 코드

import sys
from collections import deque
from itertools import combinations

input = sys.stdin.readline

directions = [(1,0),(-1,0),(0,1),(0,-1)]

def BFS(green,red):
    visited = [[[-1, -1] for i in range(m)] for i in range(n)]

    queue = deque()
    for x,y in green:
        visited[x][y] = [0,0]
        queue.append((x,y,0))
    for x,y in red:
        visited[x][y] = [0,1]
        queue.append((x,y,1))

    flowers = 0

    while queue:
        x,y,color = queue.popleft()
 
        if visited[x][y][1] == 3:
            continue
 
        for dx,dy in directions:
            sx,sy = x+dx,y+dy
            if 0<=sx<n and 0<=sy<m and graph[sx][sy] == 1:
                if visited[sx][sy][0] == -1:
                    visited[sx][sy] = [visited[x][y][0] + 1, color]
                    queue.append((sx, sy, color))

                elif visited[sx][sy][1] != color and visited[sx][sy][1] != 3:
                    if visited[sx][sy][0] == visited[x][y][0] + 1:
                        flowers += 1
                        visited[sx][sy][1] = 3

    return flowers

n,m,x,y = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))

grounds = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            graph[i][j] = 1
            grounds.append((i,j))

max_flowers = 0
for green in combinations(grounds, x):
    remain = [g for g in grounds if g not in green]
    for red in combinations(remain,y):
        max_flowers = max(max_flowers, BFS(green,red))

print(max_flowers)