240506 [BOJ/백준] 14620. 꽃길

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

---

나의 코드

def check(si, sj, visited):  # 다섯군데가 다 범위안에 들고 방문하지 않은 곳을 체크하는 함수
    for k in range(5):
        ni = si + di[k]
        nj = sj + dj[k]
        if not (0 <= ni < N and 0 <= nj < N and not visited[ni][nj]):
            return False

    return True


def cal_sum(si, sj):  # 다섯군데의 합을 구하는 함수
    sum_v = 0
    for k in range(5):
        ni = si + di[k]
        nj = sj + dj[k]
        sum_v += field[ni][nj]
    return sum_v


def flower(r, cnt, visited, S):  
    global result
    if cnt == 3:     # 3개의 꽃을 피웠을 때 최솟값 구하기
        result = min(result, S)
        return

    for i in range(r, N-1):  
        for j in range(1, N-1):
            if check(i, j, visited): # 체크했을 때 True가 반환된다면 방문하고 꽃 하나를 피우고 다섯군데의 합을 더한 값을 다시 넣는다.
                for k in range(5):
                    ni = i + di[k]
                    nj = j + dj[k]
                    visited[ni][nj] = 1
                flower(i, cnt+1, visited, S+cal_sum(i, j))

                for k in range(5): 
                    ni = i + di[k]
                    nj = j + dj[k]
                    visited[ni][nj] = 0


N = int(input())
field = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*N for _ in range(N)]
di = [0, 0, 1, 0, -1]
dj = [0, 1, 0, -1, 0]
result = 20001

flower(1, 0, visited, 0)
print(result)

 

결과

---

그래프 문제라 쉬울 줄 알았지만 힘들었다...ㅎㅎ 결국 진우코드보고 해결!