📝 배운 것들
🏷️ 위상 정렬
https://blog.encrypted.gg/1020
위상 정렬 : 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬
위상 정렬 조건 : 사이클이 없는 단방향 그래프 (DAG, Directed Acyclic Graph) = 뒤를 돌아보지 않는 상남자 그래프면 위상 정렬 가능
위상 정렬 상에서 제일 앞에 오는 원소로 가능한거 : 자신보다 앞에 위치해야 하는 정점이 하나도 없다 = 자신에게 들어오는 간선이 없다
간선 읽으면서 indegree 테이블 채우고
0인것들 큐에 다 넣은 다음에
꺼낸 다음에 정렬 결과에 추가하고
정점에서 연결된 모든 정점의 indegree 값을 1 감소시킨다
큐가 빌 때까지 반복
근데 이걸로 어제 못 풀었던 임계경로 어떻게 푼다는거지
⚔️ 백준
📌 1948 임계경로
일단 "사이클이 없다"에서 위상 정렬 문제일 수도 있다고 생각했어야 했을듯
최대 시간을 가진 경로인지 아닌지 걸러서 최적화하기 위해
위상 정렬 방식을 사용하는 건가?
while queue:
start = queue.popleft() # 이번 정점
# 다음으로 갈 정점들에 대한 정보 갱신
for next, time in city[start]:
city_indegree[next] -= 1 # indegree 하나 줄이고
# 최대 시간이 아니었다면 넘어가기
if city_time[start]+time < city_time[next]:
continue
# 걸린 시간이 같았다면 경로 cnt 추가해주기
elif city_time[start]+time == city_time[next]:
for cnt in city_cnt[start]:
city_cnt[next].append(cnt+1)
# 최대 시간이었다면 소요 시간과 경로 cnt 덮어쓰기
else:
city_time[next] = city_time[start]+time
city_cnt[next] = []
for cnt in city_cnt[start]:
city_cnt[next].append(cnt+1)
# indegree가 0이 됐으면 큐에 추가
if city_indegree[next] == 0:
queue.append(next)# indegree가 0이 됐으면 큐에 추가를 맨 아래에 뒀더니
최대 시간 걸린 경로가 아닌 놈의 경로가 좀 더 길었다면 큐에 더 들어가지 못하고 끊어져버림
순서 바꾸니까 각 경로마다 이제까지 지나온 정점 개수 잘 출력하긴 하는데 중복을 제거 못함
그냥 cnt가 아니라 간선에 대한 정보를 담아야 하는건가?
n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
city={i:[] for i in range(n+1)}
city_time = [0 for _ in range(n+1)] # 경로 가지수 제거 용도
city_history = [[] for _ in range(n+1)] # 최대 시간 경로 세는 용도
city_indegree = [0 for _ in range(n+1)] # 위상 정렬 용도
# 경로 받기
for _ in range(m):
s,a,t = map(int,input().split())
city[s].append((a,t)) # s: 출발, a: 도착, t: 걸리는시간
city_indegree[a]+=1
start_city, arrive_city = map(int,input().split()) # 시작과 마지막 도시
# 위상 정렬로 각 경로마다의 최대 시간 경로들만 남길 수 있도록 하기
# 친절하게도 출발 도시로부터 시작하라고 알려줌
from collections import deque
queue = deque()
queue.append(start_city)
while queue:
start = queue.popleft() # 이번 정점
# 다음으로 갈 정점들에 대한 정보 갱신
for next, time in city[start]:
city_indegree[next] -= 1 # indegree 하나 줄이고
# indegree가 0이 됐으면 큐에 추가
if city_indegree[next] == 0:
queue.append(next)
# 최대 시간이 아니었다면 넘어가기
if city_time[start]+time < city_time[next]:
continue
# 최대 시간이었다면 소요 시간 덮어쓰고 경로 history 초기화
elif city_time[start]+time > city_time[next]:
city_time[next] = city_time[start]+time
city_history[next] = []
# 걸린 시간이 같거나 크다면 경로 cnt 추가해주기
city_history[next].append((start,next))
for road in city_history[start]:
if not road in city_history[next]:
city_history[next].append(road)
print(city_time[arrive_city])
print(len(city_history[arrive_city]))믿었던 위상 정렬마저 시간 초과 뜸
일단 최적화를 좀 더 해보자
import sys
input = sys.stdin.readline이거 추가했지만 똑같음
간선이 아니라 정점의 개수로 세야 되는건가? 생각해봤는데 그러면 간선들이 서로 교차할 때 오류 날 것 같음
일단 질문 게시판 가봤는데 역방향 탐색을 해야 된다고 함.
어째서? 그냥 출발이랑 도착만 바꾸는거 아닌가? 결국 똑같은거 아님?
일단 테케들은 다 맞는 걸로 봐서 로직은 안 틀린듯
# 최대 시간이었다면 소요 시간 덮어쓰고 경로 history 초기화
elif city_time[start]+time > city_time[next]:
city_time[next] = city_time[start]+time
city_history[next] = set()
# 걸린 시간이 같거나 크다면 경로 cnt 추가해주기
city_history[next].add((start,next))
for road in city_history[start]:
city_history[next].add(road)오 경로 중복 안되게 하려고 set로 바꿨더니 빠르게 올라가다가 19%에서 메모리 초과 뜸
경로 세는거 아니면 메모리 초과가 날 일이 없는데
그럼 경로에 대한 정보를 갖고 있으면 안된다는거고
경로에 대한 정보 없이 경로 중복을 판별하는게 가능한거임???
city_history[next].clear()
# city_history[next] = set()파이썬은 변수에 담는게 전부 참조라고 알고 있어서
참조 자체의 데이터를 지워주면 메모리가 줄어들지 않을까 해서 재초기화 대신 clear를 해봤는데 이것도 똑같이 메모리 초과. 순간의 데이터가 아니라 사용된 데이터 기준인가?
질문 게시판 보니까 같은 python인데 dfs로 해도 30%나 가서야 시간 초과가 난다는 걸 보니까 내가 뭔가 진짜 크게 크게 잘못 생각하고 있는 것 같다.
import sys
from collections import deque
input = sys.stdin.readline
N = int(input()) # N: 도시의 개수
M = int(input()) # M: 도로의 개수
time = [0] * (N+1)
in_degree = [0] * (N+1)
graph = [[] for _ in range(N+1)]
bgraph = [[] for _ in range(N+1)] # backward of graph
cnt = [[] for _ in range(N+1)]
for _ in range(M):
# a: 출발 도시, b: 도착 도시, c: 걸리는 시간
a, b, c = map(int, input().split())
graph[a].append((c, b))
bgraph[b].append(a)
in_degree[b] += 1
src, dst = map(int, input().split())
q = deque([])
# 도시, 지나온 경로 개수
q.append(src)
while q:
# now: 도시, c: 지나온 경로의 개수
now = q.popleft()
# i[0]: 비용, i[1]: 도시
for i in graph[now]:
in_degree[i[1]] -= 1
# 비용이 갱신 될 때
if time[i[1]] < time[now] + i[0]:
time[i[1]] = time[now] + i[0]
# 달려야 하는 도로의 수 갱신
cnt[i[1]] = [now]
elif time[i[1]] == time[now] + i[0]:
cnt[i[1]].append(now)
# 선행 도로를 모두 지나갔을 때
if in_degree[i[1]] == 0:
q.append(i[1])
q = deque([dst])
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[dst])
print(len(route))그냥 답지 봄. 하... 개간단하네. 내일 다시 확인해봐야겠다.
