첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 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개 이하이다.
출력
첫째 줄에 피울 수 있는 꽃의 최대 개수를 출력한다.
입력 예시
2 2 1 1
2 1
1 2
출력 예시
2
풀이
그래프 탐색시뮬레이션 문제. 초기 배양액을 뿌릴 수 있는 경우의 수는 최대 (10개의 장소중 G개의 초록 배양액을 뿌리는 조합) x (10 - R 개의 장소 중 G개의 초록 배양액을 뿌리는 조합)이 된다. 각각의 조합에 대해 그래프 탐색을 진행하도록 하자.
현재 주기에서 방문할 수 있는 좌표들과, 좌표 타입(r, g)을 가지고 시작한다.
각 좌표의 상하좌우 중방문 가능한 좌표를 저장한다. 이 때, 방문 가능한 좌표의 타입 역시 저장한다.
앞서 저장한 방문 가능한 좌표들은 이 주기에서 방문된 모든 좌표들을 포함한다. 이 좌표들을 방문한 좌표로 바꾸어주고, 다음 두 가지 경우를 처리한다.
좌표 타입이 한 가지일 경우 : 다음 주기에 방문할 좌표로 저장한다.
좌표 타입이 여러 가지일 경우 : 이 경우 두 배양액이 동시에 만났다는 의미이므로, 꽃이 피어났다고 볼 수 있다. 따라서 다음 주기에 방문할 좌표로 저장할 필요가 없다. 또한 꽃이 피어났으므로 1을 카운트한다.
더 이상 방문할 수 없을 때까지 위 과정을 반복하면, 이 조합에서 피어날 수 있는 총 꽃송이 수가 모두 카운트된다. 모든 조합에 대해 위 알고리즘을 시행하도록 하자.
...파이썬으로는 시간초과가 나는 건 둘째치고, 다른 풀이에 비해 훨씬 더 많은 시간이 소요된다. 아마 주기마다 함수가 호출되는 문제가 원인으로 추정된다. 한 개의 큐를 사용해 풀이했어야 하나 싶다.
풀이 코드
from itertools import combinations
from collections import defaultdict
import sys
input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
N, M, G, R = map(int, input().split())
map_list = [list(map(int, input().split())) for _ in range(N)]
start_list = list()
for i in range(N) :
for j in range(M) :
if map_list[i][j] == 2 :
start_list.append((j, i))
def bfs_ones(q, visited) :
next_dict = defaultdict(set)
next_q = list()
cnt = 0
for x, y, typ in q :
for k in range(4) :
ax, ay = x + dx[k], y + dy[k]
if -1 < ax < M and -1 < ay < N and map_list[ay][ax] and not visited[ay][ax] :
next_dict[(ax, ay)].add(typ)
for (x, y), val in next_dict.items() :
visited[y][x] = True
if len(val) > 1 :
cnt += 1
continue
next_q.append((x, y, list(val)[0]))
return next_q, cnt
def search(q, visited) :
result = 0
while q :
q, cnt = bfs_ones(q, visited)
result += cnt
return result
answer = 0
for r_val in combinations(range(len(start_list)), R) :
left_list = [ x for x in range(len(start_list)) if x not in r_val]
for g_val in combinations(left_list, G) :
q = list()
visited = [[False]*M for _ in range(N)]
for r in r_val :
x, y = start_list[r]
visited[y][x] = True
q.append((x, y, 0))
for g in g_val :
x, y = start_list[g]
visited[y][x] = True
q.append((x, y, 1))
result = search(q, visited)
answer = max(answer, result)
print(answer)
