[BOJ/백준] 18809 Gaaaaaaaaaarden 파이썬

문제 링크 : https://www.acmicpc.net/problem/18809

18809번: Gaaaaaaaaaarden

 

BFS, 백트레킹, 조합 다 써볼수 있는 좋은 문제라고 생각한다.

 

문제는 비교적 간단하다.

요약하면 아래와 같다.

배양액의 종류는 두개이고 이 배양액을 놓을 수 있는 칸은 최대 10개 이하로 정해져있다.

배양액을 넣을 수 있는 칸에 주어진 배양액 전부 적절히 분배하고 확산시킨다.

이때 배양액은 동서남북 방향으로 퍼지며 물로는 갈 수 없다.

만약 배양액이 퍼지면서 동시간에 같은 칸에 들어갈 경우 해당 칸에는 꽃이피고 해당칸에서는 더이상 배양액이 퍼지지 않는다.

이때 피어나는 꽃의 최대개수를 구하라이다.

 

문제를 보면 배양액을 넣을 수 있는 칸을 골라야하고, 고른 칸에 두종류의 배양액 중 어떻게 나눠서 넣을지, 그리고 배양액을 퍼트리면서 꽃을 세야한다.

그래서 배양액을 넣을 칸은 조합으로 짰고, 각 칸에 넣을 수 있는 배양액을 고르는 것은 재귀,백트래킹으로, 마지막으로 퍼트리는 것은 BFS로 구현했다.

 

 

1. 배양액 넣을 칸 구하기

이것은 조합을 짜면 된다.

배양액을 넣을 수 있는 칸 중에서 넣을 배양액의 총개수 만큼 고르면 된다.

파이썬의 조합 메서드를 이용하자.

 

    for pos in combinations(candidate,g+r):
        select_color(select,0,pos,[g,r])

candidate에는 배양액을 넣을 수 있는 칸을 저장한 것이다. 이중에서 g+r개 만큼 뽑아서 조합을 만들라는 내용이다.

 

2. 넣을 배양액의 조합을 짜자.

이는 재귀로 구현했다.

위에서 배양액이 들어갈 칸을 정했다.

고른 첫번째 칸부터 해당 칸에 넣을 배양액의 종류를 정해서 넣는다.

주의할 점은 종류마다 배양액의 수가 정해져있으므로 개수를 줄여줘야한다.

이부분을 체크안해줘서 계속 틀리고 있었다.

def select_color(select,now,pos,cnt):
    global answer
    if now == g+r:
        answer = max(answer, simul(pos, select))
        return

    if cnt[0] > 0:
        cnt[0] -= 1
        select[now] = 1
        select_color(select,now+1,pos,cnt)
        cnt[0] += 1

    if cnt[1] > 0:
        cnt[1] -= 1
        select[now] = -1
        select_color(select,now+1,pos,cnt)
        cnt[1] += 1

cnt는 배양액의 개수를 넣었다.

현재 칸에 한번은 g배양액을 한번은 r배양액을 넣었다.

모든 칸을 다 정해줬으면 이제 BFS를 돌리자.

 

3. 배양액 퍼트리기

BFS로 구현했다.

위에서 정한칸을 q에 넣고 진행했다.

이때 두개의 배양액을 구분하기 위해서 배양액이 퍼진 시간을 하나는 음수로 하나는 양수로 했다.

방문체크도 해줘야한다. 이는 해당칸에 도달했을 때의 시간을 넣어줬다.

 

이제 가장 중요한 배양액이 동시에 접근한것을 처리 해줘야한다.

먼저 범위안에 들어오고 물이 아닌 곳인지 그리고 꽃이 핀 곳이 아닌지 체크한다.

그 다음 만약 방문하지 않았던 칸이라면 그냥 시간 증가시키고 방문체크만 해주면 된다.

 

만약 방문한 칸이라면

해당칸의 절대값이랑 나의 시간의 절대값 +1의 값이 같은지 체크한다.

절대값인 이유는 배양액 종류에 따라 음수, 양수이기 때문이다.

다음 두 값의 부호가 다른지 체크한다. 이는 같은 부호라면 같은 배양액인 것이다.

동시에 들어오고 배양액도 다른 것이라면 이제 꽃이 피는 칸이다. 그래서 해당칸에 꽃이폈다는 표시를 해주고 꽃의 개수를 증가 시킨다.

그리고 이 표시는 이전에 해당칸에 들어왔던 배양액이 더이상 퍼지지 못하게 체크를 할때 사용한다.

 

def simul(pos, order):
    visited = [[0] * m for _ in range(n)]
    q = deque()

    for idx in range(g+r):
        x,y = pos[idx]
        color = order[idx]
        visited[x][y] = color
        q.appendleft((x, y, color))

    flower_count = 0
    while q:
        x,y,t = q.pop()

        if visited[x][y] == INF:
            continue

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

            if point_validator(nx,ny,visited):
                if visited[nx][ny] == 0:
                    if t < 0:
                        visited[nx][ny] = t-1
                        q.appendleft((nx,ny,t-1))
                    else:
                        visited[nx][ny] = t+1
                        q.appendleft((nx,ny,t+1))
                elif abs(visited[nx][ny]) == abs(t)+1 and ((visited[nx][ny] < 0 and t > 0) or (visited[nx][ny] > 0 and t < 0)):
                    flower_count += 1
                    visited[nx][ny] = INF
    return flower_count

 

 

전체 소스

from sys import stdin
from collections import deque
from itertools import combinations

input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]
INF = 9876543210

n,m,g,r = map(int, input().split())
board = []
candidate = []
for x in range(n):
    board.append(list(map(int, input().split())))
    for y in range(m):
        if board[x][y] == 2:
            candidate.append((x,y))

answer = 0
def solv():
    select = [0]*(g+r)
    for pos in combinations(candidate,g+r):
        select_color(select,0,pos,[g,r])
    print(answer)
def select_color(select,now,pos,cnt):
    global answer
    if now == g+r:
        answer = max(answer, simul(pos, select))
        return

    if cnt[0] > 0:
        cnt[0] -= 1
        select[now] = 1
        select_color(select,now+1,pos,cnt)
        cnt[0] += 1

    if cnt[1] > 0:
        cnt[1] -= 1
        select[now] = -1
        select_color(select,now+1,pos,cnt)
        cnt[1] += 1

def simul(pos, order):
    visited = [[0] * m for _ in range(n)]
    q = deque()

    for idx in range(g+r):
        x,y = pos[idx]
        color = order[idx]
        visited[x][y] = color
        q.appendleft((x, y, color))

    flower_count = 0
    while q:
        x,y,t = q.pop()

        if visited[x][y] == INF:
            continue

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

            if point_validator(nx,ny,visited):
                if visited[nx][ny] == 0:
                    if t < 0:
                        visited[nx][ny] = t-1
                        q.appendleft((nx,ny,t-1))
                    else:
                        visited[nx][ny] = t+1
                        q.appendleft((nx,ny,t+1))
                elif abs(visited[nx][ny]) == abs(t)+1 and ((visited[nx][ny] < 0 and t > 0) or (visited[nx][ny] > 0 and t < 0)):
                    flower_count += 1
                    visited[nx][ny] = INF
    return flower_count
def point_validator(x,y,visited):
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
    elif visited[x][y] == INF:
        return False
    elif board[x][y] == 0:
        return False
    return True
solv()