백준 1948 임계경로 (파이썬)

https://www.acmicpc.net/problem/1948

1948번: 임계경로

나의 풀이(틀림)

위상정렬에 대한 개념을 응용해서 풀어야 하는 문제입니다.

문제에서 요구하는 정답은 두개로 하나는 도시를 탐색하는 경로의 수 그리고 나머지 하나는 모든 탐색이 끝났을때의 시간입니다.

저는 경로를 구할때 도로들이 2이상의 진입차수들의 합이라고 생각하였습니다.

 

또한 문제에서 구하는 도로를 탐색하는 인원들이 모두 모이는 시간은 다음과 같이 구현하였습니다.

1. 위상정렬을 이용해 큐에서 도시를 뽑을때마다 뽑은 도시와 연결되어 있는 다른 도시들의 간선을 줄인다.
2. 연결되어있던 도시들에 도달할수 있는 시간을 갱신해준다. (이때 모든 인원이 도착해야 하므로 최대값으로 갱신해준다.)
3. 방문하지 않은 도시들 중 집입차수가 0인 도시들의 번호를 큐에 넣어줍니다.

코드(틀림)

import sys
from collections import defaultdict, deque
input = lambda: sys.stdin.readline().rstrip()

numberOfCity = int(input())
numberOfRoad = int(input())

answerRoadCount = 1
graph = defaultdict(dict)
queue = deque()

visits = [False for _ in range(numberOfCity+1)]
times = [0 for _ in range(numberOfCity+1)]
degrees = [0 for _ in range(numberOfCity+1)]

for _ in range(numberOfRoad):
    s, e, time = map(int, input().split(" "))
    graph[s][e] = time
    degrees[e] += 1

startCity, endCity = map(int, input().split(" "))

# 경로의 수 구하기
answerRoadCount = sum([degree for degree in degrees if degree > 1])

# 모두가 모이는 최소 시간 구하기
queue.append(startCity)
visits[startCity] = True

while queue:
    now = queue.popleft()


    for nextCity, timeCost in graph[now].items():
        degrees[nextCity] -= 1
        tempTime = times[now] + timeCost
        times[nextCity] = max(times[nextCity], tempTime)

        if degrees[nextCity] == 0 and visits[nextCity] == False:
            visits[nextCity] = True
            queue.append(nextCity)

print(times[endCity], answerRoadCount,  sep = '\n')

 

그러나 채점창에서 바로 틀렸다고 나와 무엇때문에 틀렸는지 고민하였고 제가 문제를 잘못 이해해 풀었습니다...

저는 경로의 수를 구한다고 이해하여 분기들의 합으로 구하였습니다. (네비게이션 경로처럼) 그러나 문제를 다시 보니 모이는데 걸리는 최소 시간으로 오는 사람들이 지나친 도로의 수를 구하는 것이였습니다.

자력으로 여기까지 생각하기에는 무리가 있다고 판단하여 다른 사람의 코드를 참고하였습니다.

 

import sys
from collections import deque

input = sys.stdin.readline

numberOfCity = int(input())
numberOfRoad = int(input())

# 도시별 소요 시간(time), 진입 차수(in_degree), 정방향 그래프(graph), 역방향 그래프(bgraph), 경로 개수(cnt)를 저장하는 리스트 초기화
time = [0] * (numberOfCity + 1)
in_degree = [0] * (numberOfCity + 1)
graph = [[] for _ in range(numberOfCity + 1)]
cnt = [[] for _ in range(numberOfCity + 1)]

# 도로 정보를 읽고 그래프를 구성
for _ in range(numberOfRoad):
    # a: 출발 도시, b: 도착 도시, c: 소요 시간
    a, b, c = map(int, input().split())
    graph[a].append((c, b))  # 정방향 그래프
    in_degree[b] += 1  # 도착 도시의 진입 차수 증가

# 출발 도시(src)와 도착 도시(dst) 입력
startCity, endCity = map(int, input().split())

# 정방향 그래프를 이용하여 최단 시간과 경로 개수 계산
q = deque([startCity])
while q:
    now = q.popleft()
    for cost, nextCity in graph[now]:

        in_degree[nextCity] -= 1
        if time[nextCity] < time[now] + cost:
            time[nextCity] = time[now] + cost
            cnt[nextCity] = [now]

        elif time[nextCity] == time[now] + cost:
            cnt[nextCity].append(now)

        if in_degree[nextCity] == 0:
            q.append(nextCity)

# 역방향 그래프를 이용하여 최단 경로 추적
q = deque([endCity])
route = set()
while q:
    now = q.popleft()
    for x in cnt[now]:
        if (now, x) not in route:
            route.add((now, x))
            q.append(x)

# 결과 출력
print(time[endCity])  # 최단 소요 시간 출력
print(len(route))  # 최단 경로의 개수 출력

 

cnt 배열은 time 배열에 있는 값이 갱신될때마다 새로운 배열로 수정해주거나 추가해줍니다. 이렇게 함으로써 cnt로 최단 경로를 역추적할 수 있습니다.