[문제 바로가기] https://www.acmicpc.net/problem/14620
📌문제 설명
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)이 주어진다.
출력
꽃을 심기 위한 최소 비용을 출력한다.
💡 문제 풀이
문제를 읽자마자 이전에 해결한 문제들과 유사하다는 걸 파악했다...
※ 유사한 문제 : 연구소, 치킨배달, 감시 피하기 등...
복습할 겸 두 가지 방식으로 풀어보았다.
풀이 1 - 조합(combinations) 이용
조합을 이용해서 꽃을 피울 5평의 땅의 좌표를 정한다.(총 15평)
이 때, 좌표의 기준은 꽃이 완전히 폈을 때 중앙의 좌표를 기준으로 한다.
세 씨앗 모두 꽃이 펴야하므로 꽃을 피울 수 있는 행, 열의범위는 1 ~ N-1 까지다.
※ 화단의 가장자리 꽃의 중앙이 오면 화단 밖으로 꽃잎이 나가기 때문에 꽃이 죽어버린다.
최악의 경우는 N=10인 경우인데, 10x10(=100)에서 가장자리 좌표를 빼면 81(9x9)개의 후보 좌표들이 나오므로 그 중 3개를 뽑으면 81C3(=85320)개의 경우의 수가 나온다. → 조합을 사용하기 적당한 크기다.
문제 풀이 순서는 다음과 같다.
step 1)
꽃을 피울 수 있는 모든 좌표(행, 열)들을 배열에 담는다.
- candidates : 꽃을 피울 수 있는 좌표들을 담는 배열
step 2)
조합을 이용하여 candidates 중 3개의 좌표를 뽑아 해당 좌표에 꽃을 피웠을 때 모두 피울 수 있는지 확인한다.
step 3)
모든 꽃잎이 서로 닿지 않고 피울 수 있다면 해당 좌표의 대여비용을 모두 합하여 answer 변수에 최소값을 갱신한다.
- answer : 꽃을 심기 위한 최소 비용을 담을 변수
코드는 다음과 같다.
import sys
from itertools import combinations
def check(li):
global answer
visited = [] # 꽃잎이 서로 닿지 않는지 확인
total = 0 # 꽃을 피울 때 해당 좌표의 대여비용을 합할 변수
for r, c in li:
visited.append((r, c)) # 꽃의 중앙 좌표를 먼저 담는다
total += fields[r][c] # 꽃의 중앙 좌표의 대여비를 초기값으로 잡는다.
for idx in range(4): # 중앙으로부터 인접한 4방향 칸을 확인한다.
nr = r + d[idx][0]
nc = c + d[idx][1]
if (nr, nc) not in visited:
visited.append((nr, nc))
total += fields[nr][nc]
else: # 꽃잎이 서로 닿게되는 경우는 함수를 종료한다.
return
answer = min(answer, total) # 모든 꽃을 피울 수 있다면 최소 비용으로 최신화한다.
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
N = int(input())
answer = int(1e9)
fields = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
candidates = [(r, c) for r in range(1, N-1) for c in range(1, N-1)]
for li in combinations(candidates, 3):
check(li)
print(answer)풀이 2 - DFS 이용
'풀이1 - 조합'은 꽃을 피울수 있는 후보 좌표들을 미리 담아두어 진행했다면
DFS를 이용한 방법은 차례대로 탐색하면 된다.
step 1)
꽃을 피울 수 있는 좌표의 범위는 동일하다. (1 ~ N-1)
따라서 해당 범위의 행, 열 좌표에 대해 DFS 탐색을 진행한다.
- visited : 꽃을 피운 좌표를 담는 배열
- total : 꽃을 피운 자리의 대여비용 합을 담을 변수
step 2)
특정 좌표가 방문한적이 없다면 check 함수를 통해 인접한 4개의 칸에도 방문한적이 없는지 확인한다.
5개의 칸 모두 방문한적이 있으면 다음 좌표를 탐색하고
5개의 칸 모두 방문한적이 없다면 방문처리 및 대여비용을 누적시켜 진행한다.
step 3)
DFS의 종료조건은 3개의 꽃이 모두 피었을 때이다.
visited에는 꽃을 피운 좌표를 담기 때문에 배열의 길이가 15가 되면 DFS를 종료한다.
또한, 시간 단축을 위해 DFS 진행 중 대여비용의 누적이 최소 비용보다 같거나 크면 종료한다.
코드는 다음과 같다.
import sys
def check(i, j, visited):
for idx in range(4):
ni = i + d[idx][0]
nj = j + d[idx][1]
if (ni, nj) in visited:
return False
return True
def dfs(visited, total):
global answer
if total >= answer:return
if len(visited) == 15:
answer = min(answer, total)
else:
for i in range(1, N-1):
for j in range(1, N-1):
if check(i, j, visited) and (i, j) not in visited:
temp = [(i, j)]
temp_cost = fields[i][j]
for idx in range(4):
ni = i + d[idx][0]
nj = j + d[idx][1]
temp.append((ni, nj))
temp_cost += fields[ni][nj]
dfs(visited + temp, total + temp_cost)
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
N = int(input())
answer = int(1e9)
fields = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dfs([], 0)
print(answer)코테에서 DFS/BFS가 자주나오는 만큼 다양한 유형의 DFS 문제를 풀어야 겠다.
