문제 링크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번을 동시에 지을 수 ..
문제 링크https://www.acmicpc.net/problem/1004 맞은 사람 목록을 보면 해당 풀이보다 더 간단한 풀이가 존재하는 것 같다. 어쨌든 내 경우엔 이렇게 풀었다. 좌표평면 위의 원(행성계)들이 주어지고 출발점과 도착점이 주어졌을 때, 출발점에서 도착점으로 가는 동안 원을 뚫고 가는 횟수를 최소화해야 한다.문제에서 "행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다고 가정한다."라는 조건을 주었기 때문에 쉽게 풀 수 있다. 풀이에 앞서 '점 $X$ 또는 원$X$가 원$C$에 포함된다'라는 말을 '$X$가 $C$의 경계에 걸치거나 교차하지 않으면서, $C$ 내부에 있는 상태' 라고 하겠다. 1) 출발점이나 도착점이 여러 개의 원에 포함된다면 그 원 중에서도 작은 원은 항상 큰 원에 포..