[BOJ/Python] 백준 14620번 - 꽃길

백준 #14620 꽃길

14620번: 꽃길

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

n = int(input())   # 화단 한 변 길이
garden = [list(map(int, input().split())) for _ in range(n)]   # 화단 지점당 가격

def check(i, j, visited):
  for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0), (0, 0):
    x, y = i + dx, j + dy
    if not ((0 <= x < n and 0 <= y < n) and visited[x][y]):
      return False
  return True

def calc(i, j):
  cost = 0
  for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0), (0, 0):
    x, y = i + dx, j + dy
    cost += garden[x][y]
  return cost

def dfs(x, cnt, visited, cost_sum):
  global min_cost
  if cnt == 3:
    min_cost = min(min_cost, cost_sum)
    return
  for i in range(x, n-1):
    for j in range(1, n-1):
      if check(i, j, visited):
        for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0), (0, 0):
          visited[i + dx][j + dy] = False
        dfs(i, cnt+1, visited, cost_sum + calc(i, j))
        for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0), (0, 0):
          visited[i + dx][j + dy] = True

min_cost = sys.maxsize
dfs(1, 0, [[True for _ in range(n)] for _ in range(n)], 0)
print(min_cost)

백트래킹으로 쉽게 풀 수 있는 문제! 시간 복잡도를 넉넉하게 줘서 어렵지 않게 로직을 떠올릴 수 있었다. 다만, dfs 함수 내에서 틀린 게 좀 있어서 96퍼센트에서 계속 못 넘어갔음 😰

1. 화단의 바깥 부분은 심을 수 없기 때문에 그 부분을 제외한 안쪽을 탐색한다.
2. check 함수에서 꽃이 심어져있는지 여부를 표시하는 visited 리스트로 해당 위치에 꽃을 심을 수 있는지 확인한다.
3. 심을 수 있는 경우 visited 리스트에 해당 위치에 꽃을 심었다고 표시한다. (이때 다섯 평 모두 표시됨)
4. calc 함수로 해당 위치 비용을 계산하여 이전에 심었던 꽃들의 위치 비용들과 합해준다. (cost_sum)
5. cnt로 현재 심은 꽃이 몇 개인지 표시하여 cnt가 3이 되었을 때 최소 비용을 갱신해준다.
6. 재귀가 끝난 후 방문 처리 해제를 위해 False로 표시했던 visited를 다시 True로 변경한다.