백준 1948번: 임계경로 (DFS)

문제링크:1948번: 임계경로 (acmicpc.net)

1948번: 임계경로

이 문제의 조건은 먼저 n개의 노드와 m개의 가중치가 있는 일방향 간선들이 있을때, 임의의 시작 노드와 도착 노드가 정해 졌을 때에 시작 노드로부터 도착 노드로까지의 가장 큰 가중치의 합을 가진 경로를 찾고, 그 경로에 사용된 간선들의 개수를 반환하는 문제이다. 문제의 조건으로는 당연히 간선들 사이에 사이클은 존재하지 않고, 가장 큰 가중치 합을 가진 경로는 여러 개 일 수 있다는 것이다. 나는 DFS를 사용하여 시작노드부터 도착 노드까지 각 노드 별 최대 도착 가중치 합을 찾고, 도착 노드에서 DFS로 역추적하여 제일 오래 걸리는 경로들을 찾아 내는 방법을 사용하였다.

 

import sys
from collections import deque
sys.setrecursionlimit(999999)

n=int(sys.stdin.readline().rstrip())
m=int(sys.stdin.readline().rstrip())

graph=[[] for _ in range(n+1)]
rgraph=[[] for _ in range(n+1)]
for _ in range(m):
    a,b,c=map(int,sys.stdin.readline().rstrip().split())
    graph[a].append([b,c])
    rgraph[b].append([a,c])

s,e=map(int,sys.stdin.readline().rstrip().split())

maxtime=[0 for _ in range(n+1)]
visited=[0 for _ in range(n+1)]
visited[s]=1

def dfs(node,time):
    for x in graph[node]:
        new=x[0]
        newtime=x[1]
        if visited[new]==1:
            continue
        if maxtime[new]<time+newtime:
            visited[new]=1
            maxtime[new]=time+newtime
            dfs(new,time+newtime)
            visited[new]=0
dfs(s,0)

rvisited=[0 for _ in range(n+1)]
rvisited[e]=1
maxroad=0

def rdfs(node):
    global maxroad
    for x in rgraph[node]:
        new=x[0]
        newtime=x[1]        
        if rvisited[new]==1:
            if maxtime[node]-newtime==maxtime[new]:
                maxroad+=1
                continue
        if rvisited[new]==0:
            if maxtime[node]-newtime==maxtime[new]:
                rvisited[new]=1
                maxroad+=1
                rdfs(new)
rdfs(e)

print(maxtime[e])
print(maxroad)

나중에 역추적을 해야 하기에 그래프의 반대 방향 그래프 rgraph를 만들었고, maxtime은 각 노드 별 최대 도착 시간이다. dfs()함수를 통해 경로를 조사해 가는데 만약 maxtime[new]<time+newtime 으로 새로운 탐색한 경로가 기존 노드의 maxtime보다 클 때에만 dfs로 재귀하여 조사해 가며 가지치기를 하였다.

 

그 후 rdfs()함수를 사용하여 도착 노드부터 조사하였다. 아까 각 노드의 maxtime을 조사하였는데, 만약 현재 노드 node 의 maxtime에서  탐색 노드 new 까지의 걸린 시간 newtime을 뺸 것이 maxtime[new] 라면 해당 간선은 우리가 찾는 제일 오래 걸리는 경로 중 하나이므로 maxroad에 카운트 1을 올려 주고 rvisited에 저장 해 준다. rvisited[new]==1: 인 경우에도 조사 해 주는 이유는, 한 노드에서 뻗는 두개의 간선이 둘 다 제일 오래 걸리는 경로일 수 있기 때문이다.

 

예시로 1->2->3->5, 1->2->4->5 모두 제일 오래 걸리는 경로라면 rdfs()과정에서 5->3->2->1에서 rvisited[2]==1 처리 된다. 만약 rvisited가 1일때를 탐색하지 않는다면 두번째 경로를 탐색할 때 5->4->2(rvisited[2]==1) 에서 탐색하지 못하고 끝나게 될 것이다. 만약 rvisited가 1일때, maxtime[node]-newtime==maxtime[new]에 해당한다면 그 간선도 제일 오래 걸리는 경로이기에 maxroad에 카운트 해주고, 대신 new노드에서 역으로 뻗는 노드들은 이미 탐색을 완료했기에 더이상 rdfs() 해주지는 않는다. 처음에 rdfs() 함수를 만들 때 위 조건을 생각하지 못해서 틀렸었다. 그렇게 하면 maxroad에 제일 오래 걸리는 경로들의 간선들의 개수가 저장된다.