반응형 플로이드와샬4 백준 2224번 명제 증명 - C++ 풀이 1. 전건과 후건을 각각 그래프의 노드로 생각하고, 전건에서 후건으로 가는 간선을 추가한다. 2. 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면 P => Q를 증명할 수 있다. 3. 플로이드와샬을 사용하여 모든 순서쌍 (p, q)에 대해 p에서 q로 가는 경로가 있는지 확인한다. 1. 전건과 후건을 각각 그래프의 노드로 생각하고, 전건에서 후건으로 가는 간선을 추가한다. 주어지는 명제들의 전건과 후건을 각각 그래프의 노드라고 생각하자. 그리고 전건과 후건을 방향 간선(전건->후건)으로 잇는다. 2. 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면 P => Q를 증명할 수 있다. 완성된 그래프에서 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면, P => Q를 증명할 수 있다는 의미이다. 3... 2023. 8. 21. 백준 11780번 플로이드 2 - C++ 풀이 1. 플로이드 와샬 알고리즘을 사용하여 모든 도시 쌍에 대해 최단 거리를 구한다. 2. 플로이드 와샬 알고리즘을 수행할 때 이전 방문 도시 before를 함께 기록한다. 3. before를 이용하여 시작 도시에서 도착 도시까지의 루트를 구한다. 1. 플로이드 와샬 알고리즘을 사용하여 모든 도시 쌍에 대해 최단 거리를 구한다. 플로이드 와샬 알고리즘을 사용하여 O(N^3)에 모든 노드 쌍에 대해 최단 거리를 구할 수 있다. 2. 플로이드 와샬 알고리즘을 수행할 때 이전 방문 도시 before를 함께 기록한다. 플로이드 와샬 알고리즘에서 i -> j로 가는 것보다 i -> k -> j로 k를 거쳐가는 것이 더 빠를 때 거리를 업데이트한다. i에서 j로 가는 길에 k를 방문하므로, i에서 j로 갈 때 이전 방.. 2022. 7. 25. 백준 2610번 회의준비 - C++ 풀이 1. 각 사람이 리더일 때 의사전달시간의 최댓값은 플로이드 와샬 알고리즘을 사용하여 구할 수 있다. 2. 위원회는 그래프의 연결 요소와 같다. 3. DFS/BFS를 사용하여 각 위원회의 리더를 정한다. 1. 각 사람이 리더일 때 의사전달시간의 최대값은 플로이드 와샬 알고리즘을 사용하여 구할 수 있다. A가 리더일 때 B의 의사전달시간은 A와 B의 사이의 거리와 같다. 따라서 A가 리더일 때 의사전달시간의 최댓값은 나머지 모든 사람들과의 거리를 알면 구할 수 있다. 플로이드 와샬 알고리즘을 사용하여 모든 사람들에 대해 각 사람이 리더일 때의 의사전달시간의 최댓값을 구할 수 있다. 2. 위원회는 그래프의 연결 요소와 같다. 위원회의 정의는 그래프의 연결요소와 같다. 따라서 K는 연결요소의 수와 같다. 3. .. 2022. 7. 15. 백준 14938번 서강그라운드 - 스위프트(Swift) 풀이 1. 모든 정점에 대해 각 정점에서 모든 정점으로 가는 거리를 플로이드 와샬 알고리즘을 사용하여 구한다. 2. 모든 정점에 대해 해당 정점과의 거리가 m이하인 정점들을 탐색하여 해당 정점에 낙하했을 때 얻을 수 있는 아이템 수를 구한다. 3. 2번에서 구한 값 중 최댓값을 출력한다. 1. 모든 정점에 대해각 정점에서 모든 정점으로 가는 거리를 플로이드 와샬 알고리즘을 사용하여 구한다. 각 정점에 낙하하는 모든 경우를 고려한 뒤 최적해를 골라야 한다. 또한, 어떤 정점에 낙하했을 때 얻을 수 있는 아이템 수를 알려면, 해당 정점에서 나머지 정점으로의 거리를 전부 알아야 한다. 따라서 모든 정점에 대해 나머지 정점으로의 거리를 구하는 플로이드 와샬 알고리즘을 사용한다. N=100이므로 O(N^3)도 제한시간.. 2022. 1. 26. 이전 1 다음 반응형
