Computer Science/코딩테스트 문제 풀이
[백준] [파이썬] [백트래킹] 18809번: Gaaaaaaaaaarden
- -
문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
18809번: Gaaaaaaaaaarden 문제 보러 가기
제한시간: 2초
메모리 제한: 512 MB
문제
길고 길었던 겨울이 끝나고 BOJ 마을에도 봄이 찾아왔다. BOJ 마을에서는 꽃을 마을 소유의 정원에 피우려고 한다. 정원은 땅과 호수로 이루어져 있고 2차원 격자판 모양이다.
인건비 절감을 위해 BOJ 마을에서는 직접 사람이 씨앗을 심는 대신 초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피울 것이다. 이 때 배양액을 뿌릴 수 있는 땅은 미리 정해져있다.
배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다.
아래는 초록색 배양액 2개를 뿌렸을 때의 예시이다. 하얀색 칸은 배양액을 뿌릴 수 없는 땅을, 황토색 칸은 배양액을 뿌릴 수 있는 땅을, 하늘색 칸은 호수를 의미한다.
초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 땅에서는 두 배양액이 합쳐져서 꽃이 피어난다. 꽃이 피어난 땅에서는 배양액이 사라지기 때문에 더 이상 인접한 땅으로 배양액을 퍼트리지 않는다.
아래는 초록색 배양액 2개와 빨간색 배양액 2개를 뿌렸을 때의 예시이다.
배양액은 봄이 지나면 사용할 수 없게 되므로 주어진 모든 배양액을 남김없이 사용해야 한다. 예를 들어 초록색 배양액 2개와 빨간색 배양액 2개가 주어졌는데 초록색 배양액 1개를 땅에 뿌리지 않고, 초록색 배양액 1개와 빨간색 배양액 2개만을 사용하는 것은 불가능하다.
또한 모든 배양액은 서로 다른 곳에 뿌려져야 한다.
정원과 두 배양액의 개수가 주어져있을 때 피울 수 있는 꽃의 최대 개수를 구해보자.
입력
첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다.
그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양액을 뿌릴 수 있는 땅을 의미한다.
배양액을 뿌릴 수 있는 땅의 수는 R+G개 이상이고 10개 이하이다.
출력
첫째 줄에 피울 수 있는 꽃의 최대 개수를 출력한다.
예제 입력 1
3 3 2 1
2 1 0
1 0 1
2 1 2
예제 출력 1
2
예제 입력 2
4 3 1 1
0 2 0
2 1 2
0 1 0
1 1 1
예제 출력 2
1
BFS, 백트레킹, 조합 다 써볼수 있는 좋은 문제이다.
문제 요약
- 배양액의 종류는 두개이고 이 배양액을 놓을 수 있는 칸은 최대 10개 이하로 정해져있다.
- 배양액을 넣을 수 있는 칸에 주어진 배양액 전부 적절히 분배하고 확산시킨다.
- 이때 배양액은 동서남북 방향으로 퍼지며 물로는 갈 수 없다.
- 만약 배양액이 퍼지면서 동시간에 같은 칸에 들어갈 경우 해당 칸에는 꽃이피고 해당칸에서는 더이상 배양액이 퍼지지 않는다.
이때 피어나는 꽃의 최대개수를 구하라
결과적으로
1. 배양액을 넣을 수 있는 칸을 골라야하고
2. 고른 칸에 두 종류의 배양액 중 어떻게 나눠서 넣을지
3. 그리고 배양액을 퍼트리면서 꽃을 세야한다.
1. 그래서 배양액을 넣을 칸은 조합으로 짜고,
2. 각 칸에 넣을 수 있는 배양액을 고르는 것을 백트래킹으로,
3. 마지막으로 퍼트리는 것은 BFS로 구현한다.
1. G와 R 배양액을 넣을 위치(칸)들 구하기
조합을 이용
if __name__=="__main__":
N,M,G,R=map(int, input().split()) # N,M은 행열, G는 개수, R 개수
board=[]
candidate=[]
# 0은 호수, 1은 배양액을 뿌릴 수 없지만 퍼진는 땅, 2는 배양액을 뿌릴 수 있는 땅
for i in range(N):
board.append(list(map(int, input().split())))
for j in range(M):
if board[i][j]==2: # 배양액을 뿌릴수 있음
candidate.append([i,j]) # 배양액을 뿌릴 수 있는 후보군 선정
ans=0
select=[0]*(G+R)
for pos in combinations(candidate,G+R): # G개랑 R개 모두 G+R개만큼 뽑음
DFS(0,pos,[G,R]) # 배양액의 위치 조합, 배양액이 들어갈 칸을 정한다
print(ans)candidate에는 배양액을 넣을 수 있는 칸을 저장하였다. 이중에서 G+R개 만큼 뽑아서 조합을 만든다.
2. 배양액을 넣을 수 있는 칸들에 각 G와 R 배양액을 어떤 순서로 넣을 지, 칸의 조합에 넣을 배양액의 조합을 짠다.
백트래킹을 이용해서 각 순서가 정해지면 BFS를 통해 각 배양액을 퍼트려서 꽃이 핀 개수를 각 조합별 꽃 개수를 구해서 가장 큰 꽃 개수를 출력한다.
# select color
# 예: 0번째는 G(1), 1번째는 G(1), 2번째는 R(-1)로 순서별 배양액 표기를 통해 조합 만들기
def DFS(L,pos,cnt): # pos는 위치 조합
global ans
if L==G+R:
ans=max(ans,BFS(pos,select)) # 배양액 위치 조합별 꽃 최대 개수를 구한다
return
else:
# 초록 배양액 진행 상황
if cnt[0]>0:
cnt[0]-=1 # G가 0이 될때까지 배양액을 뿌려
select[L]=1 # 배양약 사용 여부 체크, G은 1로 표기
DFS(L+1,pos,cnt)
cnt[0]+=1
# 빨강 배양액 진행상황
if cnt[1]>0:
cnt[1]-=1
select[L]=-1 # 배양약 사용 여부 체크, R은 -1로 표기
DFS(L+1,pos,cnt)
cnt[1]+=1cnt는 각 배양액의 개수를 나타낸다. cnt[0]은 G, cnt[1]은 R
1. 배양액을 넣을 수 있는 칸들 중 배양액을 넣기로 한 칸들의 조합과 2. 그 칸들에 어떤 순서로 어떤 배양액을 넣을 껀지 조합을 구했다면, 3. 각 배양액을 퍼트리고 만나는 지점에 꽃을 피워 꽃의 개수를 구하자.
3. 각 배양액 퍼트리고 꽃 피운 다음 꽃 개수 세기
위에서 정한 배양액 칸을 Q에 넣고 진행한다.
이때, 서로 다른 2개의 배양액을 구분하기 위해, 각 배양액의 퍼진 시간을 하나는 음수로, 하나는 양수로 증가하며 표기한다.
또한, 중복방문을 막기 위해 방문체크도 해주어야 한다. 방문체크 2차원 배열에는 각 배양액의 퍼진 시간을 표기한다.
이때 처리해줘야 할 가장 중요한 점은 배양액이 동시에 접근하는 것이다.
1. 먼저, 퍼질때 퍼지는 위치가 물이 아니고
2. 이미 꽃이 핀 곳이 아닌지 체크
1. 만약 첫 방문이라면 시간을 증가시켜 방문체크
2. 만약 이미 방문한 칸이면 현재 퍼지는 시간과 이미 방문한 칸의 기록된 퍼진 시간이 절대값으로 같다면
3. 그게 서로 음수, 양수 (즉, 서로 다른 배양액이 만난거라면) 꽃이 핀다.
4. 핀 꽃 카운트
INF=sys.maxsize
dx=[-1,0,1,0]
dy=[0,-1,0,1]
def BFS(pos,select):
visited=[[0]*M for _ in range(N)] # 2차원 배열, board랑 똑같은, 어떤 배양액이 퍼지는지 표기하기 위해
Q=deque()
for i in range(G+R): # 배양액들 모두 사용
x,y=pos[i]
color=select[i]
visited[x][y]=color # 어떤 배양액이 퍼지는지 표기
Q.append([x,y,color]) # 조합을 통해 지정한 위치별 배양액 색을 넣어준다
# 이제 배양액을 뿌를 수 있는 위치 조합중 하나의 조합 위치에 배양액을 모두 뿌림, 이때 어떻게 퍼지는지를 BFS를 통해 본다.
flower_cnt=0
while Q:
x,y,c=Q.popleft()
if visited[x][y]==INF: # 꽃이 피면 INF
continue
for k in range(4): # 동서남북
nx=x+dx[k]
ny=y+dy[k]
if 0<=nx<N and 0<=ny<M: # 범위가 지도 안에 있어야함
if visited[nx][ny]!=INF and board[nx][ny]!=0: # 새 위치가 꽃이 핀곳이 아니면서 호수가 아니여야 함
if visited[nx][ny]==0: # 첫방문이면
if c<0: # color가 음수 즉, R인 경우
visited[nx][ny]=c-1 # R인 음수를 퍼트리면서 시간 정보를 표기함
Q.append([nx,ny,c-1]) # R이 퍼진 새 위치와 시간 정보를 넣어줌
else: # color가 양수 즉, G인 경우
visited[nx][ny]=c+1 # G인 양수를 퍼트리면서 시간 정보를 표기함
Q.append([nx,ny,c+1]) # G가 퍼진 새 위치와 시간 정보를 넣어줌
else: # 재방문인 경우
if abs(visited[nx][ny])==abs(c)+1: # 새 위치의 시간정보와 현재 위치의 색 + 1이 같으면 즉 꽃이 필 조건이면
if (visited[nx][ny] < 0 and c > 0) or (visited[nx][ny] > 0 and c < 0): # R과 G가 만나거나 또는 G와 R이 만나는 경우
flower_cnt += 1 # 꽃 개수
visited[nx][ny] = INF # 그 위치에 꽃이 핌
return flower_cnt최종 정답 코드
import sys
from collections import deque
from itertools import combinations
input=sys.stdin.readline
INF=sys.maxsize
dx=[-1,0,1,0]
dy=[0,-1,0,1]
def BFS(pos,select):
visited=[[0]*M for _ in range(N)] # 2차원 배열, board랑 똑같은, 어떤 배양액이 퍼지는지 표기하기 위해
Q=deque()
for i in range(G+R): # 배양액들 모두 사용
x,y=pos[i]
color=select[i]
visited[x][y]=color # 어떤 배양액이 퍼지는지 표기
Q.append([x,y,color]) # 조합을 통해 지정한 위치별 배양액 색을 넣어준다
# 이제 배양액을 뿌를 수 있는 위치 조합중 하나의 조합 위치에 배양액을 모두 뿌림, 이때 어떻게 퍼지는지를 BFS를 통해 본다.
flower_cnt=0
while Q:
x,y,c=Q.popleft()
if visited[x][y]==INF: # 꽃이 피면 INF
continue
for k in range(4): # 동서남북
nx=x+dx[k]
ny=y+dy[k]
if 0<=nx<N and 0<=ny<M: # 범위가 지도 안에 있어야함
if visited[nx][ny]!=INF and board[nx][ny]!=0: # 새 위치가 꽃이 핀곳이 아니면서 호수가 아니여야 함
if visited[nx][ny]==0: # 첫방문이면
if c<0: # color가 음수 즉, R인 경우
visited[nx][ny]=c-1 # R인 음수를 퍼트리면서 시간 정보를 표기함
Q.append([nx,ny,c-1]) # R이 퍼진 새 위치와 시간 정보를 넣어줌
else: # color가 양수 즉, G인 경우
visited[nx][ny]=c+1 # G인 양수를 퍼트리면서 시간 정보를 표기함
Q.append([nx,ny,c+1]) # G가 퍼진 새 위치와 시간 정보를 넣어줌
else: # 재방문인 경우
if abs(visited[nx][ny])==abs(c)+1: # 새 위치의 시간정보와 현재 위치의 색 + 1이 같으면 즉 꽃이 필 조건이면
if (visited[nx][ny] < 0 and c > 0) or (visited[nx][ny] > 0 and c < 0): # R과 G가 만나거나 또는 G와 R이 만나는 경우
flower_cnt += 1 # 꽃 개수
visited[nx][ny] = INF # 그 위치에 꽃이 핌
return flower_cnt
# select color
def DFS(L,pos,cnt): # pos는 위치 조합
global ans
if L==G+R:
ans=max(ans,BFS(pos,select)) # 배양액 위치 조합별 꽃 최대 개수를 구한다
return
else:
# 초록 배양액 진행 상황
if cnt[0]>0:
cnt[0]-=1 # G가 0이 될때까지 배양액을 뿌려
select[L]=1 # 배양약 사용 여부 체크, G은 1로 표기
DFS(L+1,pos,cnt)
cnt[0]+=1
# 빨강 배양액 진행상황
if cnt[1]>0:
cnt[1]-=1
select[L]=-1 # 배양약 사용 여부 체크, R은 -1로 표기
DFS(L+1,pos,cnt)
cnt[1]+=1
if __name__=="__main__":
N,M,G,R=map(int, input().split()) # N,M은 행열, G는 개수, R 개수
board=[]
candidate=[]
# 0은 호수, 1은 배양액을 뿌릴 수 없지만 퍼진는 땅, 2는 배양액을 뿌릴 수 있는 땅
for i in range(N):
board.append(list(map(int, input().split())))
for j in range(M):
if board[i][j]==2: # 배양액을 뿌릴수 있음
candidate.append([i,j]) # 배양액을 뿌릴 수 있는 후보군 선정
ans=0
select=[0]*(G+R)
for pos in combinations(candidate,G+R): # G개랑 R개 모두 G+R개만큼 뽑음
DFS(0,pos,[G,R]) # 배양액의 위치 조합, 배양액이 들어갈 칸을 정한다
print(ans)
코테 때 이런 모든 경우를 다 고려 해서 풀 수 있을까....?
'Computer Science > 코딩테스트 문제 풀이' 카테고리의 다른 글
| [백준] [파이썬] [DP] [위상정렬] 21276번: 계보 복원가 호석 (1) | 2023.10.05 |
|---|---|
| [백준] [파이썬] [DP] [위상정렬] 1005번: ACM Craft (1) | 2023.10.05 |
| [백준] [파이썬] [백트래킹] 16987번: 계란으로 계란치기 (0) | 2023.10.04 |
| [백준] [파이썬] [Graph] 1325번: 효율적인 해킹 (0) | 2023.10.03 |
| [백준] [파이썬] [Graph] 5214번: 환승 (0) | 2023.10.03 |
Contents
소중한 공감 감사합니다