[백준/파이썬][Gold IV] 떡 돌리기 - 20007

[Gold IV] 떡 돌리기 - 20007

문제 링크

성능 요약

메모리: 119248 KB, 시간: 236 ms

분류

데이크스트라, 그래프 이론, 최단 경로, 정렬

제출 일자

2025년 2월 9일 01:42:25

문제 설명

군인인 성현이는 전역 후에 새 집으로 이사를 갔다. 주변 이웃과 친하게 지내고 싶은 마음에 이웃집에 떡을 돌리기로 했다. 떡은 한번에 하나씩만 들고 갈 수 있다. 집들 사이에는 총 M개의 양방향 도로가 있다. 귀찮은 성현이는 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다. 또 잠은 꼭 본인 집에서 자야 하므로 왕복할 수 없는 거리는 다음날 가기로 다짐한다. N-1개의 이웃집 모두에게 떡을 돌리기 위해서는 최소 며칠이 소요될 것인가.

집의 번호는 0번부터 N-1번까지 차례대로 붙어있다.

 

 

 

입력

첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y < N)

두번째 줄부터 M+1번째 줄까지 A와 B 그리고 A집과 B집 사이의 도로의 길이 C가 주어진다. (0 ≤ A,B < N, 1 ≤ C ≤ 10,000) 단, A와 B는 서로 다른 수이고, C는 정수이다.

단, A집과 B집을 연결하는 도로는 유일하다.

 

 

 

출력

성현이의 집을 Y 라고 할 때, 이웃집 모두에 떡을 돌리기 위한 최소 일을 출력한다. 만약 모두 방문할수 없으면 -1을 출력한다.

 

 

 

풀이

import heapq

INF = float('inf')

def deijkstra(start, edges, N) :
    q = []
    heapq.heappush(q, (0, start))

    distnaces = [INF] * N
    distnaces[start] = 0

    while q:
        distance, node = heapq.heappop(q)

        for (nxt_dist, nxt_node) in edges[node] :
            new_dist = nxt_dist + distance
            if distnaces[nxt_node] > new_dist :
                distnaces[nxt_node] = new_dist
                heapq.heappush(q, (new_dist, nxt_node))

    return distnaces

def main() :
    # 이웃집 개수, 양방향 도로 개수, 피로도 제한, 내 집
    N, M, X, Y = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M) :
        A, B, C = map(int, input().split()) # A집, B집, C거리
        edges[A].append((C, B))
        edges[B].append((C, A))

    distances = deijkstra(Y, edges, N)

    # 일, 이동 거리 계산
    day = cost = 0

    # 문제점 발생 : 갔다 온다는 설정은 어떻게 해야 할까.
    # 집에 갔다가 그 자리에서 다시 나가는거 설정을 어떻게 할까

    trips = []
    for i in range(N) :
        if i == Y :
            continue
        if distances[i] == INF :
            print(-1)
            return
        trips.append(2 * distances[i])

    trips.sort()    # 가까운 집부터 처리

    days = daily_sum = 0
    for trip in trips :
        # 하루 이동 한도보다 혼자 왕복 거리가 더 크다면 배달 불가능
        if trip > X :
            print(-1)
            return
        # 현재 날짜에 더 가도 한도를 넘지 않으면 같은 날 배달
        if daily_sum + trip <= X :
            daily_sum += trip
        else :
            # 한도를 넘는다면 하루를 마치고 다음 날 시작
            days += 1
            daily_sum = trip

    # 남은 누적 이동 거리가 있다면 마지막 날 추가
    if daily_sum > 0 :
        days += 1

    print(days)

main()

 

다익스트라 알고리즘 구현

def deijkstra(start, edges, N) :
    q = []
    heapq.heappush(q, (0, start))

    distnaces = [INF] * N
    distnaces[start] = 0

    while q:
        distance, node = heapq.heappop(q)

        for (nxt_dist, nxt_node) in edges[node] :
            new_dist = nxt_dist + distance
            if distnaces[nxt_node] > new_dist :
                distnaces[nxt_node] = new_dist
                heapq.heappush(q, (new_dist, nxt_node))

    return distnaces

 

주요 포인트

• 초기화:
  • distances 리스트는 시작 노드(start)로부터 각 노드까지의 최단 거리를 저장합니다.
  • 모든 노드는 초기값을 무한대(INF)로 설정한 후, 시작 노드의 거리는 0으로 설정합니다.
• 우선순위 큐 초기화:
  • q = [(0, start)]
    • (현재까지의 거리, 노드) 형태의 튜플을 사용합니다.
    • 시작 노드부터 탐색하기 위해 (0, start)를 큐에 넣습니다.
• 메인 루프 (while q:):
  • heapq.heappop(q)로 가장 짧은 거리의 노드를 꺼냅니다.
  • 이미 처리된 경로 확인:
    • if distances[node] < dist: 조건을 사용하여, 현재 꺼낸 경로보다 이미 더 짧은 경로가 기록되어 있다면 해당 경로는 무시합니다.
• 인접 노드 탐색:
  • 현재 노드의 모든 인접 노드에 대해,
    • new_dist = dist + nxt_dist를 계산합니다.
    • 만약 new_dist가 현재 저장된 distances[nxt_node]보다 작다면,
      • distances[nxt_node]를 업데이트하고,
      • 새로운 경로 정보를 (new_dist, nxt_node) 형태로 우선순위 큐에 추가합니다.
• 리턴 값:
  • distances 리스트를 반환하여, 시작 노드에서 각 노드까지의 최단 거리를 제공합니다.

 

메인 함수

입력 처리 및 그래프 구성

def main() :
    # 이웃집 개수, 양방향 도로 개수, 피로도 제한, 내 집
    N, M, X, Y = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(M) :
        A, B, C = map(int, input().split()) # A집, B집, C거리
        edges[A].append((C, B))
        edges[B].append((C, A))

 

다익스트라 호출 및 배달 대상 집 선정

    distances = deijkstra(Y, edges, N)

    trips = []
    for i in range(N) :
        if i == Y :
            continue
        if distances[i] == INF :
            print(-1)
            return
        trips.append(2 * distances[i])
        
   trips.sort()    # 가까운 집부터 처리

• 최단 거리 계산 :
  • dijkstra(Y, edges, N)를 호출하여, 내 집(Y번 집)에서 다른 모든 집까지의 최단 거리를 구합니다.
• 배달 대상 선정 :
  • 내 집 (i == Y)은 배달 대상에서 제외
  • 만약 어떤 집에 도달할 수 없다면(distances[i] == INF), 문제의 조건에 따라 -1을 출력하고 종료
  • 왕복 거리 계산 :
    • 각 집에 대해, 편도 거리 distances[i]에 2를 곱하여 왕복 거리를 계산한 후 trips 리스트에 추가
• 정렬 : 
  • trips.sort()를 호출하여, 가까운 집부터 배달 계획을 세울 수 있도록 정렬

 

하루 배달 스케줄 계산

days = daily_sum = 0
for trip in trips :
    # 하루 이동 한도보다 혼자 왕복 거리가 더 크다면 배달 불가능
    if trip > X :
        print(-1)
        return
    # 현재 날짜에 더 가도 한도를 넘지 않으면 같은 날 배달
    if daily_sum + trip <= X :
        daily_sum += trip
    else :
        # 한도를 넘는다면 하루를 마치고 다음 날 시작
        days += 1
        daily_sum = trip

# 남은 누적 이동 거리가 있다면 마지막 날 추가
if daily_sum > 0 :
    days += 1

print(days)

• 변수 설명 :
  • days : 배달에 필요한 총 일수를 저장
  • daily_sum : 현재 날에 누적하여 걸은 왕복 거리를 저장
• 루프를 통해 배달 스케줄 계산 :
  • 각 배달 대상 집의 왕복 거리 trip에 대해 순회
  • 단일 배달 불가능 조건 :
    • 만약 한 집의 왕복 거리가 하루 이동 한도 X보다 크다면, 해당 집은 어떤 날에도 배달이 불가능 하므로 -1을 출력하고 종료
  • 하루 내 배달 가능 여부 체크 :
    • if daily_sum + trip <= X :
      • 현재까지 걸은 거리(daily_sum)에 다음 집의 왕복 거리를 더했을 때 하루 한도 X이하이면, 같은 날 배달이 가능
      • 이 경우 daily_sum에 해당 trip을 추가
    • 새로운 날 시작 :
      
      • 그렇지 않다면 (즉, daily_sum + trip > X 인 경우)
        • 현재 날에는 더 이상 배달할 수 없으므로, days를 1 증가시켜 하루를 마감
        • 그리고 daily_sum을 현재 trip 값으로 초기화하여 새로운 날의 첫 배달로 설정
• 최종 처리 :
  • 루프가 끝난 후, daily_sum이 0보다 크다는 것은 마지막 날에 배달한 집이 있다는 의미이므로, 마지막 날에 추가
  • 최종적으로 days에 필요한 총 배달 일수를 출력

 

전체적인 동작 요약

1. 입력 처리 및 그래프 구성 :
   • 집의 개수, 도로 정보, 하루 이동 한도, 내 집의 번호를 입력받아 양방향 그래프를 구성
2. 최단 거리 계산 (다익스트라 알고리즘) :
   • 내 집(Y번 집)에서 모든 집까지의 최단 거리를 계산
   • 만약 어떤 집이 도달 불가능 하다면, 바로 -1 출력
3. 배달 대상 선정 및 왕복 거리 계산 : 
   • 내 집의 제외한 각 집의 편도 거리에 2를 곱하여 왕복 거리를 계산한 후, 가까운 순서대로 정렬
4. 배달 일수 계산 (그리디) : 
   • 정렬된 왕복 거리들을 하나씩 더해가면서, 하루 이동 한도 X 내에 배달할 수 있는 만큼 처리
   • 만약 추가 배달이 한도를 초과하면, 하루를 종료하고 다음 날로 넘김
   • 하루 한도보다 한 번의 왕복 거리가 크면 배달 자체가 불가능 하므로 -1을 출력
5. 결과 출력 :
   • 배달에 필요한 최소 일수 출력