[코드트리][Python] 수들의 합 최대화하기

https://www.codetree.ai/trails/complete/curated-cards/challenge-max-sum-of-numbers/description

Code Tree | Learning to Code with Confidence

 

코드

def back_tracking(cur_num):
    if cur_num == n:
        sum_ans.append(sum(answer))
        return

    for i in range(n):
        if col[i]:
            continue

        col[i] = True

        answer.append(grid[cur_num][i])

        back_tracking(cur_num + 1)

        answer.pop()

        col[i] = False


n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]

# Please write your code here.
row = [False for _ in range(n)]
col = [False for _ in range(n)]
answer = []
sum_ans = []

back_tracking(0)
print(max(sum_ans))

 

풀이

문제는 스도쿠처럼 가능한 특정 행과 특정 열의 조합을 만들어 최대 합을 구하는 문제입니다.

주의할 점은 이중 for문으로 이중 리스트를 완전 탐색하지않게 해야합니다.

따라서 한 행마다 한 열을 선택하고, 함수의 파라미터로 '열'을 넣어주고, 행은 visited 리스트로 같은 행이 다음에 호출되는 재귀 함수에서 선택되지않게 풀어주었습니다.

 

잘못된 풀이(이중 for문으로 완전탐색하는 코드)

def back_tracking(cur_num):
    if cur_num == n:
        sum_ans.append(sum(answer))
        return

    for i in range(n):
        for j in range(n):
            if row[i] or col[j]:
                continue

            row[i] = True
            col[j] = True

            answer.append(grid[i][j])

            back_tracking(cur_num + 1)

            answer.pop()

            row[i] = False
            col[j] = False


n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]

# Please write your code here.
row = [False for _ in range(n)]
col = [False for _ in range(n)]
answer = []
sum_ans = []

back_tracking(0)
print(max(sum_ans))