[백준] 18809번 : Gaaaaaaaaaarden

18809번: Gaaaaaaaaaarden

18809번: Gaaaaaaaaaarden

🤔 문제분석

파이썬의 조합 라이브러리를 활용하여 초록색 씨앗과 빨간색 씨앗 후보를 모두 부르트포스 하여 문제를 해결하였습니다. 초록색 씨앗과 빨간색 씨앗의 후보가 생성되었다면, 씨앗을 퍼트려야합니다. 너비우선탐색을 활용하였습니다. 너비 우선 탐색을 활용한 이유는 너비우선탐색은 최단거리 탐색을 우선으로 탐색하기때문에 초록색 씨앗과 빨간색 씨앗이 동시에 접하는 부분을 탐색하기위하여 사용하였습니다.

💻 코드

import sys
input = sys.stdin.readline
from itertools import combinations
from collections import deque

def BFS():
    flower = 0
    while queue:
        y,x,ylast,xlast,time,color = queue.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 dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ny, nx = y+dy, x+dx
            if N>ny>=0 and M>nx>=0 and garden[ny][nx]:
                queue.append((ny,nx,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 _ in range(N)]
        queue = deque()
        
        for y,x in Glist:
            visited[y][x] = 1
            queue.append((y,x,y,x,1,1)) # 초록색 씨앗
            
        for y,x in GRlist:
            if visited[y][x]:
                continue
            queue.append((y,x,y,x,1,-1)) # 빨간색 씨앗
      
    visited = [[0]*M for _ in range(N)]
    result = max(result, BFS())

print(result)

🎯 피드백 및 개선사항

초록색 씨앗과 빨간색 씨앗이 동시에 접근하는 방식을 구현하기 조금 어려웠었는데, 방문배열을 조금 응용하여 문제를 해결하였습니다. 너비우선탐색 응용력을 기를 수 있는 시간이 되었습니다. 😀