플로이드-와샬

[백준 1602] 도망자 원숭이 C++

1602번: 도망자 원숭이 첫 번째 줄에는 도시의 개수 N (2 ≦ N ≦ 500) 과 도로의 개수 M (0 ≦ M ≦ 10,000), 그리고 질문의 개수 Q (0 ≦ Q ≦ 40,000) 가 주어진다. 그 다음 줄에, N개의 정수로 각 도시에서 멍멍이가 원숭이를 괴 www.acmicpc.net 플로이드-와샬 쿼리(Q)가 최대 4만개 들어온다. 출발도시와 도착도시가 주어졌을 때 플로이드 최단경로를 구하고, 경로상의 정점 중 멍멍이가 괴롭힐 수 있는 최대 시간을 구한다면 O(40000 * N^3) 으로 시간초과가 발생한다. 플로이드의 특징을 잘 생각해보자 경유하는 점은 보통 1 ~ N 번까지의 점을 순서대로 경유하도록 한다. 이는 그냥 편의를 위해서 사용하는 순서이고 경유점의 순서가 바뀌더라도 결국 A->..

선거 공약 (PROMISES)

algospot.com :: PROMISES 선거 공약 문제 정보 문제 경제가 침체기에 빠졌을 때 정치인들이 흔히 내거는 공약으로 대규모 토목 공사를 통한 경기 부양책이 있습니다. 이번에 집권당에서는 향후 N 년간 1년에 하나씩 전국 algospot.com 플로이드-와샬 문제 설명 더보기 우선 기존에 있던 고속도로들을 가지고 플로이드 알고리즘을 통해서 최단거리를 구해준다. 그리고 새로운 고속도로(a에서 b로 가는)가 건설 될 때마다 현재 최단거리와 비교해서 비용이 같거나 오히려 더 크다면 해당 고속도로를 설치할 필요가 없다. 하지만 새로운 고속도로를 설치하는게 이득이 된다면 a에서 b로 가는 고속도로를 추가하고 플로이드 알고리즘을 통해서 모든 간선의 최소비용을 갱신해 준다. r에서 c로 가는 비용을 갱신..

[백준 2458] 키 순서 C++

2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 플로이드-와샬 1. 문제 해결 아이디어 자신보다 키가 큰 게 확실한 사람, 키가 작은 게 확실한 사람들의 수를 구하면 된다. 주어진 방향그래프에서 자신이 도달할 수 있는 정점들이 모두 자신보다 키가 큰 학생임을 알 수 있다. 자신보다 키가 작은 학생들도 알아야 하므로 입력이 주어질 때 역방향 그래프도 같이 저장한다. 역방향 그래프에서 자신이 도달할 수 있는 정점들이 모두 자신보다 키가 작은 학생임을 알 수 있다. 따라서 임의의 정점에서 다른 모든 정점으로 갈 수 ..

음주 운전 단속 (DRUNKEN)

algospot.com :: DRUNKEN Drunken Driving 문제 정보 문제 As the holiday season approaches, the number of incidents caused by Driving While Intoxicated (known as DWI) increases rapidly. To prevent this, the city of Seoul has proclaimed a war against drunken driving. Every day, www.algospot.com 플로이드-와샬 문제 설명 더보기 플로이드 알고리즘은 아무 정점도 경우하지 않는 최단 거리에서 시작해 경유할 수 있는 정점을 하나씩 추가해 가며 최단 거리를 갱신한다. 이 과정에서 경유하는 정점을 1번부..

[백준 1613] 역사 C++

1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 플로이드-와샬 1. 문제 해결 아이디어 사건들의 전후 관계를 파악하는 문제라서 처음에 바로 위상 정렬로 풀기 시작했었다. 근데 위상 정렬을 해놓으니 관계도는 명확히 그려지지만 임의의 정점 2개를 선택했을 때 해당 정점들이 서로 어떤 관계에 있는지 알아보려면 매번 BFS가 필요해 보였다. 효율이 안 좋게 느껴졌고 위상 정렬은 아닌 것 같아 알고리즘 분류를 켜서 어떤 알고리즘을 써야 하는지 힌트를 받았다. 플로이드-와샬 알고리즘을 쓰는 문제였다. N이 400..

[백준 11404] 플로이드 C++

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 최단경로 플로이드-와샬 알고리즘 11404문제 예제 입력의 그래프이다 숫자가 겹쳐보이는 이유는 1 4 1 , 1 4 2 처럼 1번에서 4번 노드로 가는 경우의 비용이 중복되어서 입력되기 때문이다 플로이드-와샬 알고리즘은 동적계획법을 활용한 알고리즘이다 그래서 임의의 vertax 에서 다른 vertax로 가는 모든 경우의 수를 조사해서 최소 비용을 구할 수 있다. 그리고 다익스트라 최단거리 알고리즘은 edge의 비용이 음수인 경우는 찾지 못하는 반면 플로이드-와샬 ..