[파이썬] 백준 18809 : Gaaaaaaaaaarden (골드1)

[파이썬] 백준 18809 : Gaaaaaaaaaarden (골드1)

• https://www.acmicpc.net/problem/11660

---

풀이

방향성 생각

• 2차원 누적합을 통해서 중복 영역 계산을 피해준다.

 

---

전체코드

from collections import deque
import sys

input = lambda : sys.stdin.readline().strip()
inside = lambda x,y : 0<=x<W and 0<=y<H
dires = [(1,0),(0,1),(-1,0),(0,-1)]

H,W,A,B = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(H)]

fertilizers = []
for i in range(H):
    for j in range(W):
        if arr[i][j] == 2:
            fertilizers.append((j,i))
L = len(fertilizers)

# comb generator
def gosper(n,r):
    x = (1<<r)-1
    while x < (1<<n):
        yield x
        nx = (x|(x-1))+1
        x = nx | ((((nx&-nx)//(x&-x)) >> 1) - 1)

# brute force
answer = -1
# choose area
for choose_bit in gosper(L,A+B):
    choose_fertilizers = [fertilizers[i] for i in range(L) if (choose_bit>>i)&1]

    # A/B comb
    for comb in gosper(A+B,A):

        # BFS init
        Q = deque()
        V = [[[-1]*W for _ in range(H)] for _ in range(2)]
        for i in range(A+B):
            x,y = choose_fertilizers[i]
            state = (comb>>i)&1
            Q.append((x,y,state,0))
            V[state][y][x] = 0

        # BFS
        flowers = set()
        while Q:
            x,y,state,t = Q.popleft()
            nt = t+1

            if V[1][y][x]!=-1 and V[0][y][x]!=-1 and V[1][y][x] == V[0][y][x]:
                flowers.add((x,y))
                continue

            for dx,dy in dires:
                nx,ny = x+dx,y+dy
                if inside(nx,ny) and arr[ny][nx] and V[state][ny][nx]==-1:
                    Q.append((nx,ny,state,nt))
                    V[state][ny][nx] = nt

        answer = max(answer,len(flowers))
print(answer)

---

코멘트

• gosper's hack이라는건데, 조합을 생성할때 사용할 수 있다.
• 비트열을 사용해서 0/1로 포함유무를 나타내서 풀기.
• 굳이 리턴값으로 모든 경우의 수를 만드는 것 보다, yield를 사용해서 넘겨주기.
• BFS 구현은 차원을 하나 더 추가해서 큐에서 나오면, 그 위치가 꽃이 피는 위치인지 지정해주는 로직 추가.
• BFS가 끝나면 answer를 갱신시켜준다.
• 브루트포스에 순열 조합같은게 많은데, DFS로 구현하는 것도 좋은데 비트 이용하는 신기한 코드들이 많은듯