https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
본 문제는 가중치 없는 방향 그래프 G가 주어졌을때, 모든 정점에 대해 경로가 있는지 없는지 구하는 프로그램을 만들어야한다.
모든 정점에 대한 경로 유무를 탐색해야하므로, 그래프 탐색 알고리즘 플로이드 와샬을 써야한다.
플로이드 와샬은 시간복잡도 O(n^3)의 비용이 들정도로 다익스트라에 비해 비효율적이지만, 모든 정점에 대한 최소 비용을 알 수 있기때문에 많이 채택되는 알고리즘이다.
비효율적이지만, 코드 짜기가 매우 쉽다. 단순히 for문 3개에 relaxation만 하면 그게 플로이드 와샬 알고리즘이다.
본 문제에 대한 풀이는 다음과 같다.
1일 1백준 30일째..
'백준에 대가리 깨지는중' 카테고리의 다른 글
| [백준] 실버3 파도반 수열 (3) | 2023.06.09 |
|---|---|
| [백준] 실버1 가장 가까운 세 사람의 심리적 거리 (2) | 2023.06.07 |
| [백준] 실버1 쉬운 최단거리 (0) | 2023.06.05 |
| [백준] 실버3 조합 (0) | 2023.06.05 |
| [백준] 실버3 구간 합 구하기 4 (0) | 2023.06.01 |