5189. [파이썬 S/W 문제해결 구현] 2일차 - 전자카트

이번 문제는 사무실에서 출발해 각 구역을 한 번씩만 방문하고 사무실로 돌아올 때의 최소 배터리 사용량을 구하는 문제이다. 각 행에서 한 칸만 방문해야 하는 그런 문제인 것 같다.

물론 얘도 이것저것 해보다가 잘 안돼서 인터넷의 도움을 받았다... 이 정도면 코딩에 재능이 없는게 아닐까 싶지만, 아까부터 하품을 연달아 하는 걸 보니 그냥 졸려서 잘 안되는 것으로 생각해야겠다. (+ 팔찌 잃어버려서 멘탈 깨진 것도) 내일부턴 정신 차리고 한 문제라도 제대로 풀어야지.

T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [False for _ in range(N)]
    answer = float('inf')
    
    def dfs(count, start, total):
        global answer
        if count == N-1:
            answer = min(answer, arr[start][0] + total)
            return
        for i in range(1, N):   # 사무실로 가면 안되니 1부터
            if not visited[i] and start != i:
                visited[i] = True
                dfs(count + 1, i, total+arr[start][i])
                visited[i] = False
                
    dfs(0, 0, 0)
            
    print(f"#{test_case} {answer}")

 

아까 최소합 문제랑 지금 전자카트 문제 내일 다시 풀어봐야겠다.

 

+) 다음 날 다시 시도한 문제의 풀이: