⚔️ 백준
📌 1948 임계경로
# 해당 도시까지 걸리는 최대 시간 경로 갱신
def max_time(city):
course=set()
if city==start:
return 0
if time[city]==-1: # 아직 탐색하지 않았다면
for s,t in graph[city]:
if time[city] < max_time(s)+t: # 최대 경로가 갱신됐다면
time[city] = max_time(s)+t
return time[city]
import sys
input = sys.stdin.readline
n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
time=[-1]*(n+1) # 도시 도착 최대 시간
course=[set() for _ in range(n+1)]
graph=[[] for _ in range(n+1)] # 각 도시로 향하는 경로
# 도로 정보 받기
for _ in range(m):
s,a,t = map(int,input().split())
graph[a].append((s,t))
start,arrive=map(int,input().split())
result = max_time(arrive)
print(time[arrive])일단 어제 봤던거 응용해서 시간 구하는 건 했음
이제 경로만 구하면 됨
# 해당 도시까지 걸리는 최대 시간 경로 갱신
def max_time(city):
if city==start:
course[start].add(start)
return 0
if time[city]==-1: # 아직 탐색하지 않았다면
for s,t in graph[city]:
bef_time = max_time(s)+t
if time[city] < bef_time: # 최대 경로가 갱신됐다면
time[city] = bef_time
course[city] = course[s].copy()
elif time[city] == bef_time: # 최대 경로를 더 발견했다면
time[city] = bef_time
course[city] = course[city] | course[s]
course[city].add(city)
return time[city]
import sys
input = sys.stdin.readline
n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
time=[-1]*(n+1) # 도시 도착 최대 시간
course=[set() for _ in range(n+1)]
graph=[[] for _ in range(n+1)] # 각 도시로 향하는 경로
# 도로 정보 받기
for _ in range(m):
s,a,t = map(int,input().split())
graph[a].append((s,t))
start,arrive=map(int,input().split())
result = max_time(arrive)
print(time[arrive])
print(len(course[arrive]))짤 없이 실패
디버깅 해보니까 깊은 복사를 안해줘서 그랬음
course[city] = course[s].copy()??? 해줘도 틀렸습니다 뜬다
2
1
1 2 1
1 2
=> 1 1이 테케 돌려봤더니 1 2 뜸
그제야 뭘 잘못 생각했는지 앎
저번에 풀 때도 이거 헷갈렸었음
노드가 아니라 달린 도로를 세야됨
import sys, copy
sys.setrecursionlimit(10**5)
# 해당 도시까지 걸리는 최대 시간 경로 갱신
def max_time(city):
if city==start:
return 0
if time[city]==-1: # 아직 탐색하지 않았다면
for s,t in graph[city]:
bef_time = max_time(s)+t
if time[city] < bef_time: # 최대 경로가 갱신됐다면
time[city] = bef_time
course[city] = course[s].copy()
course[city].add((s,city))
elif time[city] == bef_time: # 최대 경로를 더 발견했다면
time[city] = bef_time
course[city] = course[city] | course[s]
course[city].add((s,city))
return time[city]
import sys
input = sys.stdin.readline
n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
time=[-1]*(n+1) # 도시 도착 최대 시간
course=[set() for _ in range(n+1)]
graph=[[] for _ in range(n+1)] # 각 도시로 향하는 경로
# 도로 정보 받기
for _ in range(m):
s,a,t = map(int,input().split())
graph[a].append((s,t))
start,arrive=map(int,input().split())
result = max_time(arrive)
print(time[arrive])
print(len(course[arrive]))ㅋㅋㅋㅋ 바꾸니까 퍼센트 올라가는데 또 그때처럼 메모리 초과 뜸
돌겠네
어쩔 수 없이 답지들을 봤다.
각 경로에 모든 이전 경로들을 저장하는게 아니라,
각 노드에서 역추적해야할 도로 1단계씩만 저장하면 됐던 거였다.
굳이 다 할 필요 없음. 그 다음엔 역추적 하면 됨...
import sys
sys.setrecursionlimit(10**5)
# 해당 도시까지 걸리는 최대 시간 경로 갱신
def max_time(city):
if city==start:
return 0
if time[city]==-1: # 아직 탐색하지 않았다면
for s,t in graph[city]:
bef_time = max_time(s)+t
if time[city] < bef_time: # 최대 경로가 갱신됐다면
time[city] = bef_time
course[city] = [s]
elif time[city] == bef_time: # 최대 경로를 더 발견했다면
time[city] = bef_time
course[city].append(s)
return time[city]
import sys
input = sys.stdin.readline
n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
time=[-1]*(n+1) # 도시 도착 최대 시간
course=[[] for _ in range(n+1)]
graph=[[] for _ in range(n+1)] # 각 도시로 향하는 경로
# 도로 정보 받기
for _ in range(m):
s,a,t = map(int,input().split())
graph[a].append((s,t))
start,arrive=map(int,input().split())
print(max_time(arrive))
from collections import deque
result=set()
q=deque()
q.append(arrive)
while q:
city=q.popleft()
for bef in course[city]:
if (bef,city) not in result:
result.add((bef,city))
q.append(bef)
print(len(result))어후 겨우 맞았습니다 봤네
이건 답지를 좀 참고했으니 나중에 다시 풀어야 될듯
역추적에 대한 아이디어를 얻어가자
탐색 자체는 역추적 안해도 되고 임계경로로 풀면 됐는듯
