5208. [파이썬 S/W 문제해결 구현] 5일차 - 전기버스2

이번 문제는 전기버스 문제이다. 전에 전기버스1 문제를 풀었던 것 같은데... 그때는 충전을 하는 거라면 지금은 교체를 한단다. 어쨌든 백트래킹을 이용해서 풀어보자.

T = int(input())
for test_case in range(1, T+1):
    arr = list(map(int, input().split()))
    N = arr.pop(0)          # 정류장 개수
    answer = float('inf')   # 최소 교체 횟수

    def bus(loc, count):    # loc: 현재 위치, count: 충전 횟수
        global answer
        if count >= answer:
            return
        if loc >= N-1:      # 출발지 index가 0이니까 N-1
            if count < answer:
                answer = count
                return
            
        for i in range(1, arr[loc]+1):  # 배터리 용량
            bus(loc+i, count+1)
    
    bus(0, -1)      # 0: 출발지 인덱스, -1: 출발지 배터리는 교체 횟수에서 제외

    print(f"#{test_case} {answer}")

이번 문제는 상당히 쉽게 풀 수 있었다. visited 리스트를 만들어야 하는지에 대한 이상한 고민을 잠깐 하기도 했지만...

처음에 입력 예시가 '5 2 3 1 1' 이런 식으로 되어 있길래, N이랑 M_i를 어떻게 구분해서 입력을 받아야 할까 고민하다가, 그냥 리스트 통째로 받고 pop(0)으로 빼내는 방법을 사용했다. 결과적으로 틀린 해결법은 아니었던 것 같다.

함수 구현할 때는 항상 파라미터로 뭘 줘야 하는지가 되게 고민이 되는데, 이번엔 일단 버스의 위치가 필요한 걸 확실히 아니까 loc을 입력하기는 했다. 근데 그 뒤에 뭘 또 줘야할까 엄청 고뇌에 빠진... 생각해보니 이번 문제는 최소 교체 횟수를 구하는 문제니까, 교체 횟수를 세는 변수가 있어야 할 것 같았다.

함수 내부 작성할 때 갑자기 머릿속이 꼬이기도 했지만 예제 가지고 이것저것(?) 하면서 어떻게든 잘 해결(?)했다...

5208. 전기버스_풀이