[SWEA] 4831. List1 - 전기버스

문제

• SWEA 4831 - (파이썬 SW 문제 해결 기본- List1) - 전기 버스
• 문제의 저작권은 SW Expert 아카데미에 있습니다.
  
  

전기 버스 문제는 정류장의 범위 안에서 최대 이동 가능 거리안에서 충전소를 최소로 방문하여 종점까지 이동하는 문제입니다.

그 충전 횟수를 반환하는 문제로 이해하는 데 까다로웠습니다. 문제를 풀고 알아보니 백 트래킹 알고리즘 방법으로 문제를 해결한 분들이 많았습니다.

따라서 백 트래킹 방법과 제가 푼 방법을 포스팅 하고자 합니다.

• 나의 코드

T = int(input())
result = []
for test_case in range(1, T + 1):
    # k : 버스의 최대 이동 가능 거리
    # n : 이동할 거리
    # m : 충전소 개수
    k, n, m = map(int, input().split())

    # 충전소 위치 인덱스 받기
    charge = list(map(int, input().split()))

    # 출발 위치와 종점 위치를 충전소 위치 양 끝에 붙임 ( 충전소까지의 거리(간격)만 파악하면 되니깐 )
    charge_route = [0] + charge + [n]

    # 출발 위치와 첫 번째 충전소, 그리고 충전소끼리의 거리를 구하는 Array를 생성한다.
    run_limit = [(charge_route[x+1]-charge_route[x]) for x in range(len(charge_route)-1)]

    # 충전 횟수 입력 받을 변수 생성
    count = 0

    # 충전소까지의 거리를 바탕으로 for문을 돈다.
    for run in run_limit:

        #충전소까지의 거리 차이가 최대 이동 거리를 넘어간다면
        if run > k:
            #결과에 0을 넣는다.
            result.append(0)
            break
    # 파이썬만의 특징인 for else문으로 break가 되지 않는다면
    # 즉, 거리 차이가 최대 이동거리를 넘지 않는다면,
    else:
        # 최대 이동거리가 이동하면서 감소되어야 하므로 k_limit이라는 변수 생성
        k_limit = k

        # 출발 지점은 이동 횟수에 포함되지 않으므로 전체 이동할 거리에서 -1 한 후, for문을 돈다.
        for i in range(len(run_limit)-1):

            # 만약 내가 이동할 수 있는 거리가 충전소 까지의 거리보다 같거나 크다면
            if k_limit >= run_limit[i]:
                # 내가 이동할 수 있는 거리를 충전소 위치 간격만큼 이동 가능 거리를 빼준다.
                k_limit -= run_limit[i]
                # 그 빼준 값이 그 다음 충전소까지 거리보다 작으면(즉, 앞으로 충전소까지 갈 거리가 이동 가능 거리 수 보다 많이 남았다면)
                if k_limit < run_limit[i+1]:
                    # 이전 충전소에서 충전을 하고 출발을 한다.
                    # 충전을 했으니 이동 가능 거리를 최대 이동 가능 거리 수로 초기화
                    k_limit = k
                    # 충전 횟수 더해주기
                    count+=1
        # 총 충전한 횟수 결과 Array에 저장.
        result.append(count)
    print(f'#{test_case} {result[test_case-1]}')

저는 충전소 위치 Array에 출발 지점과 종점을 더해 각각의 차이를 구한 Array를 새로 생성해 조건을 만족했습니다.

다음은 백 트래킹 알고리즘으로 구현한 코드입니다.

• 백 트래킹

def backtrackBus(k,n,charge):
    bus_stop = [0] * (n+1)

    #충전소 표시
    for i in charge:
        bus_stop[i] = 1
    bus = 0     # 버스 위치
    ans = 0     # 충전 횟수

    while True :
        # 버스가 이동할 수 있는 만큼 이동을 하자.
        bus+= k
        if bus >= n : break     # 종점에 도착하거나 종점을 지나 더 나아간 경우

        for i in range(bus, bus-k, -1):
            if bus_stop[i]:
                ans+=1
                bus = i
                break
        # 충전기를 못 찾았을 때
        else:
            ans = 0

    return ans

함수로 구현을 했습니다. 위에 제가 해결한 방법보다 비교적 간결?(주석 때문인지.....)합니다. 여기서 특징은 충전소의 갯수를 나타내는 변수 M을 사용할 필요가 없었습니다. 충전소 Array를 입력 받기 때문에 bus_stop에 충전소의 위치를 1로 입력을 받았기 때문입니다.

느낀점

세상엔 다양한 문제들과 풀이 방법들이 많고, 아직 포스팅 못한 문제들이 많지만 차근차근 해결한 문제들을 포스팅하며 정리해야겠다고 느꼈습니다.