문제
2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.
진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.
하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.
꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.
꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.
그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.
하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.
단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.
돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!
입력
입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.
이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.
출력
꽃을 심기 위한 최소 비용을 출력한다.
코드
def flowering(r, c): # (r, c)는 씨앗 위치(=꽃술 위치)
if r == 0 or r == n - 1 or c == 0 or c == n-1: # 맨 가장자리는 꽃을 심을 수 없음
return False
for x, y in [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)]:
nr = r + x
nc = c + y
if nr < 0 or nr >= n or nc < 0 or nc >= n or flower[nr][nc]:
return False # 꽃 심기 불가능
return True
# (r,c) 위치에 꽃 한 송이 심는데 필요한 화단 대여 비용
def get_price(r, c):
res = garden[r][c]
for x, y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr = r + x
nc = c + y
res += garden[nr][nc]
return res
# DFS
def dfs(num, price, cnt):
global ans
if cnt == 3:
ans = min(ans, price)
return
if price > ans: # 현재 가격이 ans에 저장된 최소비용보다 크다면 더 이상 볼 필요 X
return
for i in range(num+1, n**2-1-n): # 가장 끝줄은 볼 필요 없음
r = i // n
c = i % n
if flowering(r, c): # 꽃 심기 가능
for dr, dc in [(0, 0), (0,1), (0,-1), (1,0), (-1,0)]:
nr = r + dr
nc = c + dc
flower[nr][nc] = True # 꽃 심은 자리 표시
dfs(i, price+get_price(r, c), cnt+1)
for dr, dc in [(0, 0), (0,1), (0,-1), (1,0), (-1,0)]:
nr = r + dr
nc = c + dc
flower[nr][nc] = False
n = int(input())
garden = []
flower = [[False] * n for _ in range(n)] # 꽃 심은 자리
ans = 3001
for _ in range(n):
garden.append(list(map(int, input().split())))
dfs(n, 0, 0) # 맨 윗줄 볼 필요 X
print(ans)
N의 입력으로 6이 들어왔다고 할 때 아래의 표와 같이 번호를 메긴다.
0 | 1 | 2 | 3 | 4 | 5 |
6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 | 32 | 33 | 34 | 35 |
우리는 가장자리의 숫자를 빼고 보기 위해 7 ~ 28까지의 숫자만 고려하면 된다.
- flowering()
: 파라미터로 받은 (r, c)의 위치에 꽃을 심을 수 있는지 없는지 여부를 리턴. 심을 수 있다면 True. - get_price()
: 파라미터로 받은 (r, c) 위치에 꽃을 심었을 때 필요한 화단 대여 비용 리턴 - dfs()
- cnt는 심은 꽃의 수. 3이 되면 ans와 price의 값을 비교하여 둘 중 작은 값으로 ans의 값을 갱신.
- 만약 price가 ans에 저장된 최소 비용보다 이미 크다면 더이상 볼 필요가 없으므로 리턴.
- 위 표의 다음 칸에 대해 꽃을 심을 수 있다면(=flowering()이 True를 리턴한다면) 꽃을 심은 자리를 flower 배열에 True로 표시해주고 다음 칸에 대해 dfs 실행
완전탐색 풀이
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 17836번 공주님을 구해라! (0) | 2023.04.24 |
---|---|
[Python/파이썬] 백준 16234번 인구 이동 (0) | 2023.03.02 |
[Python/파이썬] 백준 9079번 동전 게임 (2) | 2023.02.28 |
[Python/파이썬] 백준 13549번 숨바꼭질 3 (0) | 2023.02.25 |
[Python/파이썬] 백준 2667번 단지번호붙이기 (0) | 2023.02.25 |