Softeer [Level 3] 나무 조경 {언어 : Python}

문제 링크

https://softeer.ai/practice/7594

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

import sys
input = sys.stdin.readline
answer = 0
n = int(input())
trees = [list(map(int, input().split())) for _ in range(n)]
selectedArr = []
last = n - 1
for r in range(n):
    for c in range(n):
        tree = trees[r][c]
        if r != last and c != last:
            selectedArr.append((r, c, r+1, c, tree+trees[r+1][c]))
            selectedArr.append((r, c, r, c+1, tree+trees[r][c+1]))
        elif r == last and c != last:
            selectedArr.append((r, c, r, c+1, tree+trees[r][c+1]))
        elif r != last and c == last:
            selectedArr.append((r, c, r+1, c, tree+trees[r+1][c]))
lenS = len(selectedArr)
def dfs(length, start, total):
    global answer
    answer = max(answer, total)
    if length == 4:
        return
    if start == lenS:
        return
    for idx in range(start, lenS):
        ar, ac, br, bc, nextV = selectedArr[idx]
        if visited[ar][ac] or visited[br][bc]:
            continue
        else:
            visited[ar][ac] = 1
            visited[br][bc] = 1
            dfs(length+1, idx+1, total+nextV)
            visited[ar][ac] = 0
            visited[br][bc] = 0
    
visited = [[0 for _ in range(n)] for _ in range(n)]
dfs(0, 0, 0)
print(answer)

풀이 방법

1. 2개씩 쌍으로 묶어서 selectedArr에 넣었다.
   1. 위에서 아래, 왼쪽에서 오른쪽 이런 방식으로 만들어서 넣었다.
2. dfs를 이용해서 겹치지 않게 total에 값을 더해준다.
3. dfs를 실행할 때마다 answer에 최대값을 치환한다.
4. answer를 반환하면 끝!

느낀점

• 더 쉽게 풀 수 있을텐데 일단은 푸는 것으로 만족했다.
• 다음에 리팩토링을 할 예정
• 문제를 잘못 읽어서 최대 4개의 쌍까지 가능하다는 말을 잘못 이해해서 4개의 쌍이 모였을 때만 answer값을 치환했다.