BeakJoon 14620. 꽃길 - 최소 비용으로 꽃 심기
3개의 좌표를 선택하는 방법은 6중포문을 쓰거나, 재귀함수를 써서 만들 수 있음 / 백트래킹을 쓰면 속도가 빠름
문제 URL: 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
1
2
3
4
5
6
7
8
6
1 0 2 3 3 4
1 1 1 1 1 1
0 0 1 1 1 1
3 9 9 0 1 99
9 11 3 1 0 3
12 3 0 0 0 1
예제 출력 1
1
12
🤩접근방법
완전탐색 문제 유형으로 board에서 3개의 좌표를 선택한 뒤, 3개의 좌표에서 1년 뒤 꽃을 정상적으로 피울 수 있는지 확인합니다.
만약 피울 수 있다면 3개의 좌표에서 화단비용을 기억해놓고, 이 비용이 다른 좌표들보다 더 싼지 비교해가며 최소 비용을 찾아나갑니다.
우선 board에서 3개의 좌표를 선택를 선택해야하는데 첫번째 방법으로 6중 포문을 활용하거나 두번째 방법으로 재귀함수를 사용하여 좌표 조합을 선택 할 수 있습니다.
선택한 3개의 좌표 집합을 구했으면 모두 확인하면서 문제에서 요구한 2가지 조건을 만족하는 좌표를 선택합니다.
- 3개의 꽃이 겹치지거나 밖으로 나가지 않고 필 수 있어야 한다.
- 최소 화단 대여 비용이여야 한다.
🤔풀이
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import sys
input = sys.stdin.readline
n = int(input())
board = [ list(map(int,input().split())) for _ in range(n) ]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def find_min_value(coordinates):
visited = [ [False for _ in range(n)] for _ in range(n) ]
value = 0
for x,y in coordinates:
visited[x][y] = True
value += board[x][y]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
if not visited[nx][ny]:
value += board[nx][ny]
visited[nx][ny] = True
else:
return -1
else:
return -1
return value
def find_combinations(board, coordinates, depth):
if depth == 3:
result = find_min_value(coordinates)
if result != -1:
global answer
answer = min(answer, result)
return
for i in range(len(board)):
for j in range(len(board[i])):
if (i, j) not in coordinates:
find_combinations(board, coordinates + [(i,j)], depth+1)
answer = 1e9
find_combinations(board, [], 0)
print(answer)
실행시간은 조합을 만들고 조건을 확인하기 때문에 느린편입니다. 이부분은 아래 코드와 같이 백트래킹 방식으로 변경하면 속도 개선이 가능합니다.
🧐
꽃을 피울 수 있는 좌표인지 확인한 뒤, 좌표를 선택/다음 조합을 위해 선택해제 하는 백트래킹 방식 으로 구현하면 실행 속도를 1700ms에서 220ms 로 줄일 수 있습니다.
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import sys
input = sys.stdin.readline
n = int(input())
board = [ list(map(int,input().split())) for _ in range(n) ]
visited = [ [False for _ in range(n)] for _ in range(n) ]
dx = [0,-1,0,1,0]
dy = [0,0,1,0,-1]
def is_right_position(x,y):
for i in range(5):
nx = x + dx[i]
ny = y + dy[i]
if not (0 <= nx < n and 0 <= ny < n):
return False
if visited[nx][ny]:
return False
return True
def find_points(board, coordinates, depth, value):
if depth == 3:
global answer
answer = min(answer, value)
return
for i in range(len(board)):
for j in range(len(board[i])):
if is_right_position(i,j):
for k in range(5):
nx = i + dx[k]
ny = j + dy[k]
visited[nx][ny] = True
value += board[nx][ny]
find_points(board, coordinates + [(i,j)], depth+1, value)
for k in range(5):
nx = i + dx[k]
ny = j + dy[k]
visited[nx][ny] = False
value -= board[nx][ny]
answer = 1e9
find_points(board, [], 0, 0)
print(answer)