SWEA 4881 - 배열 최소 합

 

처음 든 생각

- 일단 백트래킹이고 (내가 더럽게 못하는 유형)

- n-queens 문제랑 비슷한데 대각선만 빠진 형태네

- 각 열에 대해서 하나씩 선택해가면서 모든 값을 비교해봐야겠다.

 

def search(i, s):
    global result
    if s > result:
        return
    elif i == N:
        result = min(result,s)
    else:
        for j in range(N):
            if col[j] == 0:
            	// 열 방문 찍고
                col[j] = 1
                // 그 다음 행으로 넘어가서 탐색
                search(i+1, s+a[i][j])
                // 다시 복귀 -> 백트래킹
                col[j] = 0


T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    a = []
    for _ in range(N):
        a.append(list(map(int, input().split())))
    result = 1000
    // 방문 여부 체크하는 리스트
    col = [0] * N   
    search(0,0)
    print(f"#{test_case} {result}")

 

방문 여부에 따라서 이미 방문한 열은 제외하고 탐색을 하는 방식이다.

 

일단 백트래킹에 대해서 아직 내가 구현능력이 좀 많이 부족하다고 느꼈던 문제였다. (실제로 정답률 처음에 50%) 

 

백트래킹 다시 공부해야겠다.