[백준/Python]18809: Gaaaaaaaaaarden

문제

https://www.acmicpc.net/problem/18809
백준 문제집 - 0x0C강 - 백트래킹

 

알고리즘: 그래프, 브루트포스, 백트래킹, BFS, 시뮬레이션

---

풀이

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

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

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

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

 

이 문제... 나를 혼란에 빠뜨렸던 문제다...

(증거)

TypeError, NameError같은 에러가 제일 얼탱이없다

 

백트래킹 문제이지만 백트래킹을 사용하지 않고 풀었다...

 

먼저 배양액을 뿌릴 수 있는 땅의 좌표를 possible에 따로 저장해둔다.

그리고 combinations모듈을 사용해 조합을 구한다.

초록색/빨간색 배양액을 남김없이 모두 사용해야 하므로 G + R만큼의 조합을 생성한다.
생성된 조합으로 G개 만큼의 조합을 또 생성한다. 초록색 배양액을 뿌릴 수 있는 조합이다.
빨간색 배양액의 조합은 G + R 조합에서 G 조합을 제외한 나머지 조합이 되겠다.

 

초록색 배양액을 뿌릴 수 있는 좌표 green, 빨간색 배양액을 뿌릴 수 있는 좌표 red를 가지고 bfs를 시작한다.
visited를 N x M 크기만큼 생성하고, green과 red를 체크한다.
두 배양액이 만나 꽃을 피울 수 있으려면 '동일한 시간'에 같은 장소에 도달해야한다.
따라서 visited에는 (색을 구별할 값, 시간)이 저장될것이다.

(임의로 green은 1, red는 -1로 저장했다.)

green과 red를 순회하며 각 좌표에 해당 색깔, 0(초기시간)을 저장한다.
그리고 큐에도 (x, y, 색깔, 시간)을 추가한다.

 

초기셋팅이 끝나면 본격적으로 탐색을 시작하는데, 꽃이 된 경우를 제대로 체크해야한다.
나는 green부터 큐에 넣었기때문에 green -> red -> green... 순으로 진행될것이다.

초록색 배양액을 (x, y)에 뿌린 후 큐에 추가했다고 가정해보자.
초록색의 턴이 끝나면 빨간색 배양액이 (x, y)를 발견하고 해당 좌표를 꽃으로 변경할것이다.
문제를 보면 꽃으로 변한 후에는 인접한 땅으로 배양액을 퍼뜨릴 수 없다.
따라서 이미 큐에 들어가있는 (x, y)는 꽃이 된 좌표이므로 pass해야한다.

 

즉, 1) 현재 좌표가 이미 꽃인지 먼저 체크해야한다.
그 뒤 2) 동서남북으로 확장한 좌표가 호수가 아닌지 확인한다.
호수가 아닌 땅이라면 3-1) 방문하지 않은 땅인지, 3-2) 같은 시간에 다른 색 배양액이 방문했었는지 체크한다.

방문하지 않은 땅이라면 (현재 색깔, 현재 시간+1)을 visited에 저장하고 큐에 추가한다.
이미 방문한 상태라면 visited의 값이 (-현재 색깔, 현재 시간+1)인지 확인 후 꽃의 갯수를 업데이트한다. 큐는 건너뛴다!

 

참고로 이 문제는 Python3가 아닌 PyPy3로 통과했다.

 

전체 코드

# PyPy3로 통과한 코드.
# 메모리: 142476KB / 시간: 1652ms
from sys import stdin
from itertools import combinations
from collections import deque

input = stdin.readline

def bfs(green, red):
    visited = [[0] * M for _ in range(N)]
    queue = deque()
    flowers = 0

    for gx, gy in green:
        visited[gx][gy] = (1, 0)
        queue.append((gx, gy, 1, 0))
    for rx, ry in red:
        visited[rx][ry] = (-1, 0)
        queue.append((rx, ry, -1, 0))

    while queue:
        x, y, color, time = queue.popleft()

        if visited[x][y] == -1:  # 현재 좌표가 꽃이라면 continue
            continue

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0 <= nx < N and 0 <= ny < M and garden[nx][ny] != 0:
                if visited[nx][ny] == 0:  # 방문하지 않은 좌표라면 진행
                    visited[nx][ny] = (color, time+1)
                    queue.append((nx, ny, color, time+1))
                elif visited[nx][ny] == (-color, time+1):  # 다른 배양액이 뿌려진 좌표라면 꽃으로 업데이트
                    visited[nx][ny] = -1
                    flowers += 1
    return flowers


N, M, G, R = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

garden = []
possible = []
max_flowers = 0

for i in range(N):
    line = list(map(int, input().split()))
    for j in range(M):
        if line[j] == 2:  # 배양액을 뿌릴 수 있는 좌표만 따로 저장
            possible.append((i, j))
    garden.append(line)

for comb in combinations(possible, G+R):
    for green_comb in combinations(comb, G):
        green = list(green_comb)  # 만들 수 있는 초록색 배양액 좌표
        red = [c for c in comb if c not in green]  # 빨간색 배양액 좌표
        max_flowers = max(bfs(green, red), max_flowers)

print(max_flowers)

 

Python3로 통과한 풀이 자체가 별로 없다.

키포인트는 조합 생성 방식인듯한데...

백트래킹으로 조합을 생성하면 G, R 갯수에 맞게 체크하며 진행하기 때문에 계산횟수가 줄어드는듯하다.

 

combinations 모듈로 조합을 생성하게 되면 G + R개의 모든 조합을 생성 후 초록색/빨간색을 나누게된다.

따라서 순서만 바뀐 조합이 여러번 발생할 수 있다.

 

만약 배양액을 뿌릴 수 있는 좌표가 아래와 같다고 생각해보자.

[(0, 0), (1, 1), (2, 2)]

그리고 G = 1, R = 1라고 했을때 combinations로 생성된 G + R 조합은 다음과 같다.

[(0, 0), (1, 1)], [(0, 0), (2, 2)], [(1, 1), (2, 2)]

여기서 또 한번 G개만큼 초록색 배양액 조합을 생성하게 되고, 나머지를 빨간색 배양액으로 지정하는 방식이다.

그럼 아래와 같은 결과가 발생한다.

초록: (0, 0), 빨강: (1, 1)
초록: (1, 1), 빨강: (0, 0)

색만 다를뿐 시뮬레이션은 같은 케이스가 발생하는것이다.

 

헌데, 똑같이 combinations를 두번 사용해서 풀었는데도 Python3로 통과한 코드가 있다;;

사실 증거샷에서 시간초과러쉬가 난 이유도 이거였다. 로직은 같은데 왜 내껀 안되는지 이해가 안가서 무한제출을 반복했다.

이유는 아직도 알지못함. Help!