BruteForce17꽃길(14620)

문제

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

입력

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.

이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

출력

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

풀이

• dfs 이용하여 3개의 cnt 종료되었을때 까지
• 완전탐색

코드

import sys
sys.stdin = open("input.txt", "rt")
input = sys.stdin.readline

flower = [(0,0), (-1,0), (1,0), (0,-1), (0,1)]
N = int(input()) # 화단 한 변의 길이
board = [list(map(int,input().split())) for _ in range(N)] # N개의 줄에 N개씩 화단의 지점당 가격
visited = [[False]*N for _ in range(N)]
answer = 987654321

def check(y,x):
    global N
    for dy, dx in flower:
        ny = y + dy
        nx = x + dx
        if 0>ny or ny>N-1 or 0>nx or nx>N-1 or visited[ny][nx]:
            return False
    return True

def calculate(y,x):
    global N
    result = 0
    for dy, dx in flower:
        ny = y + dy
        nx = x + dx
        result += board[ny][nx]
    return result

def dfs(x, cost, cnt):
    global answer
    if cnt == 3: # 3개의 꽃 모두 다 놓았을 때 종료
        answer = min(answer, cost)
        return
    for i in range(x,N):
        for j in range(1,N):
            if check(i,j):
                visited[i][j] = True
                for dy,dx in flower:
                    visited[i+dy][j+dx] = True
                dfs(i, cost + calculate(i,j), cnt +1)
                visited[i][j] = False
                for dy,dx in flower:
                    visited[i+dy][j+ dx] = False
dfs(1,0,0)
print(answer)