[Softeer] 함께하는 효도

문제링크

---

함께하는 효도

풀이과정

---

진짜 멘탈 펑 터져버린 문제 ..

DFS를 이용하면 될거라고 생각해서 풀었으나 마음처럼 되지않는 ... 내 코드 ...

그래서 CodingJoker님의 velog를 보고 겨우 이해했다 하핫 ...

이 문제도 누가 먼저 출발하느냐에 따라 과일 수확량이 달라질 수 있기 때문에 순열을 사용했다.

그리고 출발점에서 DFS를 통해 3초내에 수확할 수 있는 수확량과 그 path를 저장한다.

이게 아이디어는 생각이 나는데 구현하는데 애를 너무 많이 먹었다 ...

코드

---

import sys
from itertools import permutations

n, m = map(int, input().split())

fruits = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
position = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]
visited = [[False] * n for _ in range(n)]

def DFS(x, y, fruit, iter, path):
    global max_fruits, max_path
    visited[x][y] = True
    fruit += fruits[x][y]
    path.append((x, y))

    if iter == 3:
        if max_fruits < fruit:
            max_fruits = fruit
            max_path = path[:]
        return

    for dx, dy in direction:
        mx, my = x + dx, y + dy
        if (0 <= mx < n and 0 <= my < n) and not visited[mx][my] and not (mx, my) in total_path:
            DFS(mx, my, fruit, iter+1, path)
            visited[mx][my] = False
            path.pop()


permu_pos = list(permutations(position, m))
result = 0

for pos in permu_pos:
    total_fruits = 0
    total_path = []

    for x, y in pos:
        max_fruits, max_path = 0, []
        DFS(x-1, y-1, 0, 0, [])
        total_fruits += max_fruits
        total_path += max_path
    result = max(result, total_fruits)

print(result)

결과

---