문제 링크
https://www.acmicpc.net/problem/18809
🕒 Python 풀이시간: 30분
import sys
from itertools import combinations
from collections import deque
dx=[0,0,-1,1]
dy=[-1,1,0,0]
input=sys.stdin.readline
N,M,G,R=map(int,input().split())
board=[]
enabled=[]
for i in range(N):
arr=list(map(int,input().split()))
for j in range(M):
if arr[j]==2:
enabled.append((i,j))
board.append(arr)
def bfs(case_g,case_r):
global board
visited=[[['N',-1] for _ in range(M)] for _ in range(N)]
q=deque()
numOfFlowers=0
for x,y in case_g:
visited[x][y][0]='G'
visited[x][y][1]=0
q.append((x,y,'G'))
for x,y in case_r:
visited[x][y][0]='R'
visited[x][y][1]=0
q.append((x,y,'R'))
while q:
now=q.popleft()
if visited[now[0]][now[1]][0]=='F':
continue
for i in range(4):
nx=now[0]+dx[i]
ny=now[1]+dy[i]
if nx<0 or ny<0 or nx>=N or ny>=M:
continue
if board[nx][ny]==0:
continue
if visited[nx][ny][0]==now[2]:
continue
if visited[nx][ny][0]=='F':
continue
if visited[nx][ny][0]=='N':
visited[nx][ny][0]=now[2]
visited[nx][ny][1]=visited[now[0]][now[1]][1]+1
q.append((nx,ny,now[2]))
elif visited[nx][ny][0]!=now[2]:
if visited[nx][ny][1]!=visited[now[0]][now[1]][1]+1:
continue
visited[nx][ny][0]='F'
numOfFlowers+=1
visited[nx][ny][1]=visited[now[0]][now[1]][1]+1
return numOfFlowers
answer=0
for case_g in list(combinations(enabled,G)):
rest=set(enabled)-set(case_g)
for case_r in list(combinations(rest,R)):
answer=max(answer,bfs(case_g,case_r))
print(answer)🌸 동시간에 만나 꽃이 피는 배양액의 마법! BFS 탐구 🧪
배양액을 가능한 경우대로 뿌린 후 동시간에 만나는 지점에서는 꽃이 피는 것을 찾는 문제이다.
먼저 동시간 대 접근성을 확인해야 하므로 BFS라는 것을 간단히 생각할 수 있다. 먼저 모든 경우를 따지기 위해 조합을 사용해준다. 배양액을 뿌릴 수 있는 칸, 즉 2번 칸에 대해서 따로 저장해주고 그 칸중에 G개를 고른다. 그런 후 G개를 고르고 남은 칸중에서 또 R개를 뽑으면 된다. 그 모든 케이스에 대해서 bfs를 수행해주면 된다.
bfs의 경우는 visited를 3차원으로 두어서 기존의 2차원 bfs에다가가 현재 칸의 상태를 표현하기 위해 한칸을 알파벳으로 두었다. F일 경우 꽃이 있는 칸인 것이고 N의 경우 아직 접근하지 못한 칸, 나머지는 R과 G이다. board에 대해서 0번 칸은 물이므로 접근 불가능하고 이미 방문했고 동일한 R과 G일 경우에도 접근 불가능하다. 이제 나머지 경우인데 아직 방문하지 못한 칸의 경우는 기존의 BFS처럼 방문해주면 되고 만약 상태가 다른데 동시간 방문이면 꽃을 피워주고 큐에 넣지 않으면 된다.
이 때, 큐에서 꺼낼 때도 현재 칸이 꽃인지 확인해 주었는데 꽃을 피우기 위해 칸에 접근할 경우에는 꽃을 피우기에 큐에 넣지 않아 진행이 되지 않지만 먼저 도착한 R이나 G의 경우에는 아직 꽃을 피우지 않았기에 이를 처리해주지 않으면 계속 확장되어 다른 칸에 영향을 줄 수 있다. 그렇기에 현재 칸이 꽃이라면 다른 배양액이 접근하여 꽃이 피여진 칸이기에 확장하면 안되므로 continue 시켜준다.
이렇게 Python로 백준의 "Gaaaaaaaaaarden" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
