📕문제

[Baekjoon] 14620. 꽃길

문제 설명

칸마다 비용이 다른 N x N 크기의 화단에서 3개의 꽃을 피울 수 있는 최소 비용을 구하는 문제다.
꽃은 심은 칸을 기준으로 상하, 좌우로 잎이 피며 서로 다른 꽃이 만나거나 화단 밖으로 나가지 않아야 한다.

---

📝풀이

import sys
read = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

N = int(read())
ground = [list(map(int, read().split())) for _ in range(N)]

cost = [[0] * (N-2) for _ in range(N-2)]

for y in range(1, N-1):
    for x in range(1, N-1):
        cost[y-1][x-1] = ground[y][x]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            cost[y-1][x-1] += ground[ny][nx]

result = sys.maxsize
visited = [[False] * N for _ in range(N)]

def isValid(x, y):
    if visited[y][x]:
        return False
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if visited[ny][nx]:
            return False
    return True

def setVisited(x, y, check):
    visited[y][x] = check
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        visited[ny][nx] = check

def dfs(depth, total):
    global result
    if total >= result:
        return
    if depth == 3:
        result = min(result, total)
        return
    for y in range(1, N-1):
        for x in range(1, N-1):
            if isValid(x, y):
                setVisited(x, y, True)
                dfs(depth + 1, total + cost[y-1][x-1])
                setVisited(x, y, False)

dfs(0, 0)
print(result)

• 꽃은 심은 칸을 포함해 상하, 좌우 총 5칸을 차지하게 되므로 심게 될 칸에 대한 총 비용을 계산에 cost에 미리 저장한다.
  모서리 부분은 꽃잎이 필 수 없기 때문에 제외한다.
• isValid: 해당 칸에 씨앗을 심을 수 있는 지 판단하는 함수다.
  해당 칸, 혹은 상하, 좌우에 꽃이 존재하면 False를 반환한다.
• setVisited: 탐색을 하며 꽃을 심거나 없앨 때 꽃의 유무를 설정하는 함수다.
  꽃을 심을 땐 해당 칸과 상하, 좌우를 True로, 꽃을 없앨 땐 False로 설정한다.
• 위 두 함수를 활용해 DFS를 진행한다.
  • depth: 현재까지 심은 꽃의 수, total: 현재까지의 비용
  • total(지금까지 계산한 비용)이 result(현재까지의 최솟값)보다 크면 탐색을 중단하고 돌아간다. (가지치기)
  • 심은 꽃의 수가 3개면 result를 total과 비교해 더 작은 값으로 업데이트 한다.
  • 방문하지 않은 나머지 칸에 대해서 재귀적으로 호출한다.