[BOJ#14620] 꽃 길

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

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

9114

4824

3388

52.131%

문제

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)이 주어진다.

출력

꽃을 심기 위한 최소 비용을 출력한다.

 

---

제출 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

di = [0, 1, -1, 0, 0]
dj = [1, 0, 0, -1, 0]

def check(si, sj, visited):
    for k in range(5):
        ni = si + di[k]
        nj = sj + dj[k]
        # (범위 안에 있고 방문되지 않은것)이 아니면 False
        # == 범위 밖이고 방문한곳이면
        if not (0 <= ni < N and 0 <= nj < N and not visited[ni][nj]):
            return False
    # 범위 안이고 방문하지 않은 곳이면
    return True

def seedsum(si, sj):
    seed = 0
    for k in range(5):
        ni = si + di[k]
        nj = sj + dj[k]
        seed += arr[ni][nj]
    return seed

def recur(si, cnt, visited, sumone):
    global result
    if cnt == 3:
        result = min(sumone, result) # 최대값 저장
        return
    # 가로배열 값을 1씩 더해서 순회한 것을 받아오기
    for i in range(si, N-1):
        for j in range(1, N-1):
            if check(i, j, visited):
                for k in range(5):
                    ni = i + di[k]
                    nj = j + dj[k]
                    visited[ni][nj] = True
                # 백트래킹
                recur(i, cnt+1, visited, sumone+seedsum(i, j))
                for k in range(5):
                    ni = i + di[k]
                    nj = j + dj[k]
                    visited[ni][nj] = False

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
# 테두리 안쪽을 돈다.

result = 10e9
# 가로 인덱스값, 꽃잎 갯수, 방문값, 꽃잎 가격
recur(1, 0, visited, 0)
print(result)

 

2차원 배열의 가장 바깥을 제외한 테두리를 돌면서 꽃잎이 피는 반경의 최소값을 구해주는 문제.

브루트 포스로 2차원 배열을 순회하는 법을 고민했지만 생각해내지 못하고 결국 합류했다..

깊이로 1씩 더해가는 부분은 한지 오래되서그런지 구현이 많이 어색해진 것 같다.

 

visited 값을 들고다니면서 check함수로 들렸던 곳인지 판별하고,

들렸던 곳이면 다음 순회로 가고 아니라면 방문표시를 해주고 꽃잎값을 더해준다.

만약 꽃잎을 3개 다 폈다면 다시 돌아가서 다른 꽃잎으로 3개를 편 경우의 최소값을 비교해준다.

주어진 입력값이 적어서 시간복잡도는 크게 신경쓰지 않아도 됐던 것 같다.