BOJ_14620 : 꽃길

👉 문제링크

14620번: 꽃길

---

---

🔸 문제 분석 🔸

• 최소비용으로 세 꽃을 심을 수 있는 최소 비용을 출력한다.
• 모든 경우의 수를 탐색해야하는 브루트 포스 문제이다. 

🔸 코드 🔸

import sys
input = sys.stdin.readline

N = int(input())
flower = []
visit = [[0]*N for _ in range(N)]
answer = 200*16
dx = [0, 0, -1, 0, 1]
dy = [0, -1, 0, 1, 0]

for i in range(N):
    n = list(map(int,input().strip().split()))
    flower.append(n)


def check(x, y):
    for i in range(5):
        if visit[x+dx[i]][y+dy[i]] == 1:
            return False
    return True

def switch(flag,x,y):
    sum = 0
    for i in range(5):
        visit[x+dx[i]][y+dy[i]] = flag
        sum += flower[x+dx[i]][y+dy[i]]
    return sum

def dfs(coin, count, x):
    global answer
    if count >= 3:
        if coin < answer:
            answer = coin
        return

    for i in range(x, N-1):
        for j in range(1, N-1):
            if check(i,j):
                dfs(coin + switch(1,i,j), count+1, i)
                switch(0,i,j)


dfs(0, 0, 1)
print(answer)

🔸 코드 해석 🔸

• dx, dy : 현위치, 좌,상,우,하 인덱스를 위한 리스트
• check(x, y) 함수 : x, y 에 꽃을 심을 수 있는지 확인
• switch(flag, x, y) : x, y 에 꽃을 심거나 심지않은 상태로 변경. 땅 가격의 합도 반환.
• dfs(coin, count, x)
  • 화단을 전부 순회하며 최소값을 찾음
  • 꽃을 3개 심으므로, dfs 재귀가 3이 될때까지 탐색
• 반복 탐색에서 x 좌표만 인자로 넘기므로, y좌표 중복검사가 생김

 

---

🔸 end 🔸

• 상당히 어려웠던 문제다. 처음 봤을땐 포기했고, 2번째에는 고민하다 답안지를 봤다.
  답지 알고리즘을 보니 풀 수 있을 것 같아서 3회차로 도전했지만, 조금씩 오류가 생겨서 결국 답안 포스팅을 참고했다.
• 브루트포스 알고리즘이 태그에 하나 있지만, bfs나 벡트래킹 등도 적용됐다.
• 처음엔 y좌표 중복검사를 구현하고자 했지만 사소한 오류가 많아져서, 코드 가독성에 더 무게를 두고 간단한 형태로 코드를 마무리했다.