데구리 블로그

문제 링크https://www.acmicpc.net/problem/5214 역들을 연결하는 하이퍼튜브가 있고, 각 하이퍼튜브가 서로 연결하는 역들이 주어질 때 1번 역에서 N번 역으로 가는데 방문하는 역의 개수의 최소값을 구해야 한다. 누가 봐도 BFS문제이지만 일반적인 방법처럼 연결된 역들을 모두 그래프로 이어버리면 메모리 초과를 받게 된다. 일반적인 방법대로 풀어보자.하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M의 범위는 $1 \leq K, M \leq 1,000$이다. 하이퍼튜브 하나당 정점끼리 $K^2$개의 간선이 연결되므로 그래프의 총 간선의 개수는 최악의 경우 $O(MK^2) = 1,000,000,000$개이다. 메모리가 터질 수밖에 없다. 중복된 간선을 여러번 연결했기 때문..

문제 링크 https://www.acmicpc.net/problem/1005 "모든 건물을 지을 수 없는 경우는 없다."라는 조건에서 주어진 그래프가 싸이클 없는 방향 그래프(DAG)라는 걸 알 수 있다. 건물을 짓는 순서가 정해져 있으므로 위상정렬로 해결할 수 있다. 단순 BFS로는 풀기 힘들다. 본문의 예제를 단계별로 살펴보자. $x$번 건물이 완성될 때까지의 총 시간을 $d[x]$으로 표현하겠다. 아직 완성 시간을 알 수 없는 건물은 0의 값을 가진다. $step\,0)$ 초기상태이다. $n$ 1 2 3 4 $d$ 0 0 0 0 $step\,1)$ 우선 1번 건물을 먼저 지을 수 있고, 10초가 걸린다. $n$ 1 2 3 4 $d$ 10 0 0 0 $step\,2)$ 2번과 3번을 동시에 지을 수 ..