풀이
가중치가 없는 방향 그래프가 주어질 때, 모든 정점 간 연결이 가능한지 아닌지를 탐색 후 인접 행렬 형식으로 표현해주면 된다.
Floyd Washall 을 사용해서 풀이했다.
가중치는 없지만, 결국 모든 탐색 가능한 정점에 대해 정점 간 연결이 존재하는 경우 또 다른 정점간의 간접적 연결이 되기 때문이다.
단, 단순히 정점간의 간접적 연결에 대한 유무 판단만 하면 되기에 아래의 조건만 충족한지 살펴보자
소스코드
출처
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 9019] DSLR [Python] (0) | 2023.04.19 |
|---|---|
| [백준 10828] 스택 [C] (0) | 2023.04.18 |
| [백준 2798] 블랙잭 [C] (0) | 2023.04.17 |
| [백준 27959] 초코바 [Python] (0) | 2023.04.17 |
| [백준 5525] IOIOI [Python] (0) | 2023.04.15 |