[백준 18809번] Gaaaaaaaaaarden (Python3)

import sys
input = sys.stdin.readline
from itertools import combinations
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]

def BFS():
  flower = 0
  while dq:
    y,x,ylast,xlast,time,color = dq.popleft()
    if visited[ylast][xlast] == 1:  #전에 꽃이 폈으면
      continue
    if visited[y][x]:
      if visited[y][x] == (time,-color):
        visited[y][x] = 1
        flower += 1
      continue
    visited[y][x] = (time,color)
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0 and garden[y1][x1]:
        dq.append((y1,x1,y,x,time+1,color))
  return flower
    

N,M,G,R = map(int,input().split())

garden = []
for i in range(N):
  garden.append([*map(int,input().split())])

spread = []
for i in range(N):
  for j in range(M):
    if garden[i][j] == 2:
      spread.append((i,j))

result = 0
for GRlist in combinations(spread,G+R):
  for Glist in combinations(GRlist,G):
    visited = [[0]*M for i in range(N)]
    dq = deque()
    for y,x in Glist:
      visited[y][x] = 1
      dq.append((y,x,y,x,1,1))  #y,x,ylast,xlast,time,color
    for y,x in GRlist:
      if visited[y][x]:
        continue
      dq.append((y,x,y,x,1,-1))
    visited = [[0]*M for i in range(N)]
    result = max(result,BFS())

print(result)

 

시뮬레이션 구현문제 치고는(?) 약간 까다로울 순 있다.

그래도 구현은 구현이고 매우 쉽다.

 

일단 처음에 배양액을 어디에다 뿌릴지를 정해야한다. 나는 python의 combinations 함수를 이용해서 nCg+r 만큼 뽑고 그 중에서 g+rCg만큼 초록색, 나머지를 빨간색으로 하는 방법을 선택했다.

 

그리고 나서 BFS한 방식은

1. BFS에서 deque에 (현 위치, 이전 위치, 시간, 색깔)의 정보를 넣는다.

2. visited에는 (시간,색깔) 로 기록한다.

3. 만약 이전 위치에서 꽃이 폈다면, continue한다. (더 이상 배양액이 퍼지면 안되므로)

3. 현 위치가 visited라면, 시간은 같고 색깔은 다를 경우 꽃의 개수를 +1 해주고, 꽃으로 표시한다.

 

나쁘지 않은 문제였다.

 

 

오늘의 교훈) 구현은 쉽다.