DHistory
[Baekjoon] Shortest Path - 11403 경로 찾기 본문
문제
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
풀이
import sys
INF = 1e9
n = int(sys.stdin.readline().rstrip())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
for index, value in enumerate(numbers):
if value:
graph[i][index + 1] = 1
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
for i in range(1, n + 1):
for j in range(1, n + 1):
print(0 if graph[i][j] == INF else 1, end=' ')
print()
채점 결과
'Computer Science > Algorithm' 카테고리의 다른 글
| [Baekjoon] Shortest Path - 1446 지름길 (0) | 2023.10.31 |
|---|---|
| [Baekjoon] Shortest Path - 1389 케빈 베이컨의 6단계 법칙 (0) | 2023.10.30 |
| [Baekjoon] Shortest Path - 1058 친구 (0) | 2023.10.30 |
| [Baekjoon] Shortest Path - 18352 특정 거리의 도시 찾기 (0) | 2023.10.30 |
| [Baekjoon] DP - 1495 기타리스트 (오답노트) (0) | 2023.10.26 |