Problem Solving/백준
[BOJ 백준] 14620번 : 꽃길(Python, 파이썬)
돌돌김
2021. 1. 29. 02:27
14620번: 꽃길
2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므
www.acmicpc.net
백트래킹을 활용하는 문제였다.
dfs 함수에서 반복문을 돌면서 백트래킹을 하는 부분을 블로그 참고해서 풀었다.
소스 코드
import sys
sys.stdin = open("input.txt", "r")
flower_dir = [(0,0),(-1,0),(1,0),(0,-1),(0,1)] # 현위치, 상, 하, 좌, 우
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
answer = 987654321
def check(y, x):
global n
for dy, dx in flower_dir:
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_dir:
ny = y + dy
nx = x + dx
result += board[ny][nx]
return result
# 3개 꽃 고르기
# 서로 겹치지 않게 하기
# 오른쪽 끝까지 갔으면 다음 줄로 넘어갈 수 있도록 하기
def dfs(x, cost, cnt):
global answer
if cnt == 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_dir:
visited[i+dy][j+dx] = True
dfs(i, cost + calculate(i, j), cnt+1)
visited[i][j] = False
for dy, dx in flower_dir:
visited[i+dy][j+dx] = False
dfs(1, 0, 0)
print(answer)