[SWEA] 5208_전기버스2 (백트랙킹 이용)

📕 문제

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

💡 풀이법

1. dfs의 n은 현재 버스가 도착한 정류장이고 c는 충전한 횟수가 된다.

2. 첫번째 정류장은 충전한 횟수에 포함되지 않기 때문에 dfs 바깥쪽에서 for문을 돌려줬다.

3. 버스가 정류장에 도착해서 충전을 했을 때 갈수 있는 곳까지 for문을 돌면서 모두 dfs를 돌려준다.

(이때, 충전 횟수는 +1이 된다)

4. 만약 가는 중에 ans보다 충전횟수가 같거나 많다면 return한다(가지치기)

5. 도착지에 도착했다면 c와 ans랑 비교해서 더 작은 값을 ans에 넣는다.

 

def dfs(n, c):
    global ans

    if c >= ans:  # 가지치기
        return
    if n == N:
        ans = min(ans, c)
        return

    end = n+battery[n-1]
    if end > N:
        end = N

    for i in range(n+1, end+1):
        dfs(i, c+1)

T = int(input())
for tc in range(1, T+1):
    nums = list(map(int, input().split()))
    N = nums[0]
    battery = nums[1:]
    ans = 100
    for i in range(2, battery[0]+2):
        dfs(i, 0)
    print('#{} {}'.format(tc, ans))