4881. [파이썬 S/W 문제해결 기본] 5일차 - 배열 최소 합

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AWTQh00qQs0DFAVT&categoryId=AWTQh00qQs0DFAVT&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=PYTHON&select-1=2&pageSize=10&pageIndex=5#

SW Expert Academy

 

#dfs함수 정의
def dfs(depth, total):
    global min_sum

    if total>min_sum:
        return

    if depth==N:
        min_sum=min(min_sum,total)
        return

    for i in range(N):
        if not visited[i]:
            visited[i]=True
            dfs(depth+1,total+arr[depth][i])

            visited[i]=False #백트레킹

T=int(input())
for tc in range(1,T+1):
    #1.입력받기
    N=int(input())
    arr=[]
    for _ in range(N):
        arr.append(list(map(int,input().split())))
    
    #2.필요한 자료형 정의
    min_sum=float('inf') #무한대
    visited=[False for _ in range(N)]
    
    #3.동작함수
    dfs(0,0) #depth,total
    
    #4.출력
    print('#{} {}'.format(tc,min_sum))

DFS로 풀 수 있을꺼라 생각을 못했어서 연습이 많이 필요함을 또 느꼈다.

 

처음에 조합을 풀었었는데 시간 초과나서 틀렸었다.

# 모든 경우의 수 체크
# 3<=N<=10, 순열 사용해도 메모리 초과 없을 듯
# ex) 3-> (1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,2,1)(3,1,2)

from itertools import permutations

T=int(input())
for tc in range(1,T+1):
    N=int(input())
    matrix=[]
    for _ in range(N):
        matrix.append(list(map(int,input().split())))

    ans=101
    num=[i for i in range(N)]
    perm=list(permutations(num,N))

    for case in perm: #(0,1,2) ->x
        tmp=0

        for x in range(N):
            tmp += matrix[x][case[x]]
            
            if tmp>ans:
                break

        ans=min(ans,tmp)

    print('#{} {}'.format(tc,ans))

 

한 달 가까이를 BFS/DFS 공부했는데 아직도 못 푸는게 살짝 현타가 온 건 비밀,,,ㅎㅎ,,,,,

열심히 하다보면 언젠가 술술 풀리겠지~~~