Explanation
하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.
단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.
돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자! 라는 문제이다.
요약을 해보자면,
1. 꽃을 심을 때는 씨앗의 위치 기준 현재위치, 상, 하, 좌, 우(5평)의 비용을 써야한다.
2. 꽃잎 또는 꽃술이 화단 밖을 벗어나면 안된다.
3. 꽃잎 또는 꽃술이 다른 꽃잎 또는 꽃술과 겹쳐선 안된다.
3개의 꽃을 피우는 최소 비용을 구하는 문제이다. 처음에는 bruteforce + bfs로 문제를 풀었다.(아주 멍청한 방법이였다.) 제대로 구현도 안될뿐더러 문제를 제대로 읽지 않아서 코드를 작성하면서 조건을 끼워넣었다.(문제 좀 제대로 읽자 !..)
Algorithm
backTracking
dfs함수에 (1,0,0)을 넘겨준다. 첫번째 인자는 꽃의 개수를 카운팅하는 변수이고, 두번째는 비용을 계산할 변수, 세번째는 꽃의 개수가 조건에 만족했을 때 최소 값을 업데이팅하기 위한 변수이다.
꽃을 피우기 위해서는 현재 위치 기준으로 상, 하, 좌, 우의 공간이 확보되어야 하므로 (1.1)에서 부터 시작한다. 각 좌표를 돌면서 check함수를 이용해 현재 위치, 상, 하, 좌, 우가 화단을 벗어나지 않고, 방문한 적이 없다면 조건을 통과한다. 그리고 각 방향마다 방문을 체크해주고, 비용을 계산 후 cnt값을 1 증가(= 현재 꽃이 핀 개수)한다.
cnt가 3이 되면(= 조건을 만족하면) min(현재까지 누적된 비용, 현재 비용)을 한다. 그 이유는 각 좌표를 순서대로 돌면서 꽃이 3개가 피었다고 하더라도 지금까지 핀 꽃의 비용보다 더 적은 비용으로 꽃을 피울 수 있다면 갱신해주어야 하기 때문이다.
import sys
input = sys.stdin.readline
n = int(input())
matrix = []
for _ in range(n):
matrix.append(list(map(int, input().split())))
visited = [[0] * (n+1) for _ in range(n+1)]
answer = float('inf')
flower_direction = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)] # 현재위치, 상, 하, 좌, 우
def check(x, y):
global n
for dx, dy in flower_direction:
nx = x + dx
ny = y + dy
if nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1 or visited[nx][ny]:
return False
return True
def init_position(x, y):
for dx, dy in flower_direction:
nx = x + dx
ny = y + dy
visited[nx][ny] = 0
return True
def calculate(x, y):
res = 0
for dx, dy in flower_direction:
nx = x + dx
ny = y + dy
res += matrix[nx][ny]
return res
def dfs(flowers, cost, cnt):
global answer
if cnt == 3:
answer = min(answer, cost)
return
for i in range(flowers, n):
for j in range(1, n):
if check(i, j):
visited[i][j] = 1
for dx, dy in flower_direction:
nx = i + dx
ny = j + dy
visited[nx][ny] = 1
dfs(i, cost + calculate(i, j), cnt + 1)
init_position(i, j)
dfs(1, 0, 0)
print(answer)Time Complexity
...
