[백준] 꽃잎

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

분류::  dfs 

 

1. 문제 이해 및 해결과정

- 모든 경우 탐색 dfs - 가능한 열매 시작점은 1~n-2,1~n-2 까지임  - 아직 선택되지 않은 열매라면, 현재 열매에서 꽃잎까지 비용모두 저장하고(cost), sum(기존값)에 더해준다 - 선택되었던 것을 취소 - cnt==3 (모두선택되면), 가능한 값들 중 최소값 저장

 

2. 풀이방법

  1. dfs

#꽃길
#https://www.acmicpc.net/problem/14620
import sys
sys.stdin = open("input.txt","r")
n=int(input())
board=[list(map(int,input().split())) for _ in range(n)] #가격
visited=[[False]*n for _ in range(n)] #방문
dh=[-1,1,0,0]
dw=[0,0,-1,1]
sol=1e9

def check(i,j):#선택된 꽃잎의 열매거나 꽆잎이면 안됨
    if visited[i][j]==True:
        return False
    else:
        for k in range(4):
            if visited[i+dh[k]][j+dw[k]]:
                return False
    return True

def dfs(cnt,sum):
    global sol
    if cnt==3:
        sol=min(sol,sum)
    else:
        for i in range(1,n-1): #꽃 열매의 시작지점
            for j in range(1,n-1):
                if check(i,j): #가능한 열매지점이라면
                    visited[i][j]=False
                    cost=board[i][j]
                    for k in range(4):
                        visited[i+dh[k]][j+dw[k]]=True #꽃잎체크
                        cost+=board[i+dh[k]][j+dw[k]] #비용
                    dfs(cnt+1,sum+cost)
                    visited[i][j] = False
                    for k in range(4):
                        visited[i + dh[k]][j + dw[k]] = False


dfs(0,0)
print(sol)

 

3. 오답원인

 

4. 알게된 점