반응형 플로이드 워샬2 [C/C++] 백준 #2458 키 순서(플로이드 워샬) #2458은 n명의 사람들중에 일부 사람들끼리 키를 비교해서 그 결과를 아는 경우에, 정확하게 자신이 몇번째 키 순서를 가졌는지 알 수 있는 사람들의 숫자를 구하라는 문제입니다. https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 처음에 접근한 방법은 위상정렬이었습니다. 하지만 위상정렬로 처리하기에는 한계가 있어서 플로이드 워샬 알고리즘을 변형해서 사용하기로 했습니다. 플로이드 워샬은 그래프에서 모든 노드간의 최소 비용 경로값을 계산해주는 알고리즘으.. 2023. 5. 11. [C/C++] 백준 #1956 운동(플로이드 워샬) 이번 문제는 전형적인 플로이드 워샬 문제입니다. 플로이드 워샬 알고리즘은 음의 가중치가 있어도 문제를 풀 수 있고, 사이클을 찾아내는데에도 유용합니다. 하지만, 반복횟수가 많기 때문에, 노드의 개수가 많은 경우에는 좋지 않습니다. 알고리즘 시간복잡도가 \(O(V^3)\)입니다. 별도의 자료구조가 필요한 것도 아니기 때문에, 알고리즘만 이해하고 있다면, 손쉽게 구현할 수 있습니다. 제가 작성한 소스입니다. //------------------------------------------------ // baekjoon #1956 // - by Aubrey Choi // - created at 2019-11-16 //------------------------------------------------ #in.. 2022. 12. 9. 이전 1 다음 728x90
