SWE(전자카트)

작성일 | In

SWE 전자카트

  • 사무실에서 출발해 각 구역을 한 번씩만 방문하고, 사무실로 돌아올 때의 최소 배터리 사용량 구하기
  • 1번은 사무실을 뜻하며, 2번부터 N번은 관리 구역 번호이다.
  • 예를 들어 N이 3인 경우 가능한 경로는 1-2-3-1, 1-3-2-1이다.(차례 차례 방문한 다음에 돌아오던가, 아니면 끝으로 가서 한번에 돌아오던가)
  • 쉽게 생각해서, 2,3의 부분집합의 개수만큼 이동 가능한 경우의 수가 생성된다
  • N이 4라면 , 2,3,4가 기준이므로 부분집합 6개가 생성될 거다.
def DFS(start):
    global sub_result, result, final_result

    if len(sub_result) == N-1:
        for i, j in sub_result:
            result += Battery[i][j]
        result += Battery[start][0]
        final_result.append(result)
        result = 0
        return

    for next in range(1, N):
        if not visited[next]:
            sub_result.append((start, next))
            visited[next] = True
            DFS(next)
            sub_result.remove((start, next))
            visited[next] = False


for rounds in range(int(input())):
    N = int(input())
    Battery = [list(map(int, input().split())) for _ in range(N)]
    visited = [0]*N
    sub_result = []
    final_result = []
    result = 0
    DFS(0)
    print('#%d %d' % (rounds+1, min(final_result)))
  • 해리님 코드를 참고하지 않으려고 했는데, 쉽지가 않았다.
  • 초기에 문제가 이해 안가서 멍때렸다..

참고자료 [SWexperacademy]https://swexpertacademy.com [참고블로그]https://tothefullest08.github.io/algorithm/2019/08/01/1_5188_최소합/

0%