99클럽 코테 스터디 2일차 TIL + 퍼레이드

문제 상황

도시들이 도로로 연결되어 있고, 매 도로에서 퍼레이드가 열릴 수 있다. 퍼레이드가 열리면 해당 도로를 사용할 수 없게 되는데, 이 때 최단 경로가 영향을 받는 정점쌍(s, t)의 개수를 각 도로별로 구하는 문제다.

단순히 보면, 도로 하나씩 막고 다익스트라를 돌리면 될 것 같지만, 그렇게 하면 시간 초과가 발생할 수 있다.

---

어떤 시도를 했는지

1. 첫 시도: 각 도로를 하나씩 제거하고 다익스트라를 수행한 뒤, 원래의 최단 경로보다 멀어진 정점들을 확인해 카운트하는 브루트포스 방식으로 구현했다.
2. 성공은 했지만 비효율적: Python에서 다익스트라를 M번 반복하는 방식은 입력 수가 많아질수록 매우 느려졌다.

---

작성 코드

# https://www.acmicpc.net/problem/16118
import sys, heapq
input = sys.stdin.readline
INF = int(1e9)

def dijkstra_for_fox(start):
    pq = []
    distance = [INF] * n
    distance[start] = 0
    heapq.heappush(pq, (0, start))

    while pq:
        cur_dist, cur_node = heapq.heappop(pq)

        if cur_dist > distance[cur_node]:
            continue

        for next_node, weight in graph[cur_node]:
            dist = cur_dist + weight
            if dist < distance[next_node]:
                distance[next_node] = dist
                heapq.heappush(pq, (dist, next_node))

    return distance

def dijkstra_for_wolf(start):
    pq = []
    distance = [[INF] * 2 for _ in range(n)]  # [빠름, 느림]
    distance[start][0] = 0  # 시작은 빠르게

    heapq.heappush(pq, (0, start, 0))  # 거리, 노드, 상태(0=빠름, 1=느림)

    while pq:
        cur_dist, cur_node, state = heapq.heappop(pq)

        if distance[cur_node][state] < cur_dist:
            continue

        for next_node, weight in graph[cur_node]:
            if state == 0:  # 다음은 느리게 감
                new_dist = cur_dist + weight // 2
                if new_dist < distance[next_node][1]:
                    distance[next_node][1] = new_dist
                    heapq.heappush(pq, (new_dist, next_node, 1))
            else:  # 다음은 빠르게 감
                new_dist = cur_dist + weight * 2
                if new_dist < distance[next_node][0]:
                    distance[next_node][0] = new_dist
                    heapq.heappush(pq, (new_dist, next_node, 0))

    return distance

# 입력
n, m = map(int, input().split())
graph = [[] for _ in range(n)]

for _ in range(m):
    a, b, d = map(int, input().split())
    d *= 2  # 정수 연산을 위해 거리 두 배로 저장
    graph[a-1].append((b-1, d))
    graph[b-1].append((a-1, d))

fox_dist = dijkstra_for_fox(0)
wolf_dist = dijkstra_for_wolf(0)

# 결과: 여우가 더 빠른 경우만 카운트
cnt = 0

for i in range(n):
    if fox_dist[i] < wolf_dist[i][0] and  fox_dist[i] < wolf_dist[i][1]:
        cnt += 1
        
print(cnt)

어떻게 해결했는지

• 블로그에서 소개한 최적화 방식은 “경로 수를 포함한 전체 쌍 최단 경로 (All-Pairs Shortest Paths)” 개념을 도입했다.
• 핵심 아이디어는:
  1. 모든 정점에서 다익스트라를 한 번씩 돌려서 dist[s][t], ways[s][t]를 모두 구한다.
  2. 각 도로(u, v)를 기준으로, 특정 (s, t)쌍에서 이 간선이 반드시 포함되어야만 최단 경로가 완성되는 조건을 수식으로 판별한다.
• 수식 조건:이 조건이 성립하면, (s, t)의 최단 경로에는 (u, v) 간선이 반드시 포함된다는 의미다.

dist[s][t] == dist[s][u] + w + dist[v][t]
ways[s][t] == ways[s][u] * ways[v][t]

• 이렇게 하면 간선을 제거하지 않고도 최단경로에 포함되는지를 정확하게 판별할 수 있다.

---

✨ 무엇을 새롭게 알았는지

• 최단 경로의 개수도 다익스트라로 구할 수 있다는 사실을 처음 알게 되었다. 동일한 거리로 도달할 수 있는 경로가 여러 개일 때는 fromCnt[v] += fromCnt[u] 식으로 누적하면 됨.
• 단순히 거리만 비교하면 안 되는 경우도 있다는 것을 체감했다. (여러 개의 경로가 있을 수 있기 때문에 경로 수 비교가 중요하다.)
• 다익스트라로 전체 쌍을 구해두면 시간복잡도는 올라가지만 전체 효율은 좋아진다는 것을 배웠다.

---

🌱 내일 학습할 것

• 플로이드-워셜 알고리즘과 다익스트라를 비교하며 정점 수에 따른 선택 기준 학습하기
• 다익스트라에서 경로 복원하는 법 복습
• 다른 그래프 최단 경로 유형(예: 벨만포드, 0-1 BFS 등)도 하나씩 정리해보기