[백준/Python] 14620번: 꽃길

문제

https://www.acmicpc.net/problem/14620

14620번: 꽃길

---

문제 요약

N × N 꽃 밭에 격자 모양의 꽃 3개를 심어야 한다.

 

꽃은 꽃술 1개와 꽃잎 2개로 이루어져 있다.

 

화단 밖으로 꽃잎이 나가거나, 서로 다른 꽃잎들이 닿게 될 경우, 꽃은 죽는다.

 

각 칸은 대여비가 존재하고, 하나의 꽃을 심을 때 5칸의 화단이 필요하다.

 

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

---

코드

# 화단 좌표 (x, y)에 꽃을 심을 수 있는지 파악하는 함수
def Isplant(x, y):
    if check[x][y]:
        return False
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if check[nx][ny]:
            return False
    return True

# 화단 좌표 (x, y)에 꽃을 심는 함수
def plant(x, y):
    global cost
    cost += arr[x][y]
    check[x][y] = 1
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        check[nx][ny] = 1
        cost += arr[nx][ny]
        #print(add)

# 화단 좌표 (x, y)의 꽃을 제거하는 함수
def unplant(x, y):
    global cost
    cost -= arr[x][y]
    check[x][y] = 0
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        check[nx][ny] = 0
        cost -= arr[nx][ny]

# 백 트래킹으로 어느 곳에 세 꽃을 심어야 가장 비용이 저렴한지 확인하는 함수
def find(cnt): 
    global res
    if cnt == 3: # 심은 개수가 3개라면
        if cost < res:
            res = cost
            #print(f"res는 {cost}로 갱신되었습니다.")
        return
    for i in range(1, N - 1):
        for j in range(1, N - 1):
            if Isplant(i, j):
                #print(f"심어볼 곳은 {(i, j)}입니다.")
                plant(i, j)
                find(cnt + 1)
                #print(f"지워질 곳은 {(i, j)}입니다.")
                unplant(i, j)

N = int(input())
# 화단 한 변의 길이

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

arr = [list(map(int, input().split())) for _ in range(N)]
# arr는 화단의 대여 비용을 저장한 배열

check = [[0] * N for _ in range(N)]
# 화단에 꽃이 있는지를 체크하는 배열

res = 200 * 15
# 가장 저렴한 비용

cost = 0
# 현재 탐색 중인 좌표에 꽃을 심었을 때 드는 비용

find(0)

print(res)

---

코드 설명

백 트래킹을 이용하여 화단에 꽃을 심을 수 있는 모든 경우의 수를 찾고 가장 싸게 세 꽃을 심을 수 있는 비용을 출력한다.

 

+ 꽃잎이 화단 밖으로 나가면 안되므로 행과 열을 인덱스 1씩 줄여 탐색한다.