(BOJ1948

• tags : (algorithm

  No matching post could be found

  - (topological sort
• 문제 링크 : https://www.acmicpc.net/problem/1948
• 풀이 링크
  • Python

• 기본적으로 최단 경로를 찾아야 하는 문제인데, 두가지를 더 고려해야 한다.
  • 최단 경로를 찾아야 하지만, 최대 시간을 구해야 하고,
  • 최대 시간이 걸리는 경로를 모두 찾아야 한다.
• 근데 여기서 조금 고민을 했는데, 문제에서 ‘이런 사람들이 지나는 도로의 수를 카운트 하여라’ 부분이 잘 이해가 가지 않았다.
  • 이 부분은 다음과 같이 설명된다.
  • 문제에서 요구하는 출발지에서 도착지까지 최대 시간을 구하고,
  • 해당 시간이 걸리는 모든 도로를 구한 다음,
  • 그 도로들을 중복 없이 세어주면 된다.
  • 예를 들어 1→2→3→5, 1→2→4→5 라는 두가지 경로가 똑같이 최대 시간으로 걸린다고 할 때, 도로의 수는 각 경로의 길이 3+3=6이 아니라, 각 도로의 수 5(1→2, 2→3, 2→4, 3→5, 4→5)를 출력해야 한다.

• 풀이 코드는 크게 3가지 부분으로 구성되어 있다.
  • 경로 탐색을 위한 설정
  • 최단 경로 최대 시간 탐색
  • 도로의 수 찾기

N = int(input())
M = int(input())
roads = [[] for _ in range(N + 1)]
in_roads = [0] * (N + 1)
for _ in range(M):
    s, e, t = MIIS()
    roads[s].append((e, t))
    in_roads[e] += 1
st, end = MIIS()

• 도로는 단방향이므로, 연결 리스트를 활용, 다음 도로를 저장하는 방식으로 구성했다.

time = [0] * (N + 1)
parent = [[] for _ in range(N + 1)]
queue = deque([(st, 0)])
while queue:
    x, t = queue.popleft()
    for y, _t in roads[x]:
        in_roads[y] -= 1
        next_time = t + _t
        if time[y] == next_time:
            parent[y].append(x)
        if time[y] < next_time:
            time[y] = next_time
            parent[y] = [x]
        if not in_roads[y]:
            queue.append((y, time[y]))

• 경로 탐색은 위상 정렬을 활용했다.
• 도로의 수를 탐색하기 위해 parent리스트를 만들었고, 경로의 시간이 최대가 될 때 부모로 추가했다.

roads_count = set()
queue = deque([end])
while queue:
    x = queue.popleft()
    for y in parent[x]:
        if (y, x) in roads_count:
            continue
        roads_count.add((y, x))
        if y != st:
            queue.append(y)

• 도로의 수를 탐색하기 위해 set을 활용했다.
  • 위에서 설명한 것 처럼, 최대 시간이 되는 모든 경로에 사용되는 도로들을 모아서 판단해야 하는데, 도로의 수를 단순하게 세어 가는 방식으로는 쉽지 않았다.
  • 그래서, 그러한 도로를 모두 set에 추가하여 갯수를 파악했다.
• 위에서 각 부모를 저장한 것을 활용했는데, 모든 부모를 탐색하는 것이 아니라, 최대 시간이 되는 경로만 탐색하므로, 따로 저장하고 활용했다.