[boj] 14620번: 꽃길

출처 : https://www.acmicpc.net/problem/14620

14620번: 꽃길

 

 

1. 문제 설명 

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다. 단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다. 돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자! 라는 문제이다. 
요약을 해보자면, 
1. 꽃을 심을 때는 씨앗의 위치 기준 `현재위치, 상, 하, 좌, 우`(5평)의 비용을 써야한다. 
2. `꽃잎 또는 꽃술`이 화단 밖을 벗어나면 안된다.
3. `꽃잎 또는 꽃술`이 다른 `꽃잎 또는 꽃술`과 겹쳐선 안된다.

 

 

 

2. 접근 방식 

dfs함수에 (1,0,0)을 넘겨준다. 첫번째 인자는 꽃의 개수를 카운팅하는 변수이고, 두번째는 비용을 계산할 변수, 세번째는 꽃의 개수가 조건에 만족했을 때 최소 값을 업데이팅하기 위한 변수이다. 꽃을 피우기 위해서는 현재 위치 기준으로 상, 하, 좌, 우의 공간이 확보되어야 하므로 (1.1)에서 부터 시작한다. 각 좌표를 돌면서 check함수를 이용해 현재 위치, 상, 하, 좌, 우가 화단을 벗어나지 않고, 방문한 적이 없다면 조건을 통과한다. 그리고 각 방향마다 방문을 체크해주고, 비용을 계산 후 cnt값을 1 증가(= 현재 꽃이 핀 개수)한다. cnt가 3이 되면(= 조건을 만족하면) min(현재까지 누적된 비용, 현재 비용)을 한다. 그 이유는 각 좌표를 순서대로 돌면서 꽃이 3개가 피었다고 하더라도 지금까지 핀 꽃의 비용보다 더 적은 비용으로 꽃을 피울 수 있다면 갱신해주어야 하기 때문이다. 

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)

 

 

4. 분석

Time :
Space :
소요시간 : 1시간 
제출 횟수 (무작정 제출하기 않기)  :  4회
어려웠던 부분과 해결한 방법 :
실수가 줄어들었는가 ?