문제
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.
출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.
예제
예제 입력 1
3
0 1 0
0 0 1
1 0 0예제 출력 1
1 1 1
1 1 1
1 1 1예제 입력 2
7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0예제 출력 2
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0문제접근
이 문제는 주어진 인접 행렬에서 양수인 경로의 존재 여부를 판별하는 문제이다.
DFS,BFS??여러가지 방법으로 풀 수 있겠지만 플로이드-와샬 알고리즘을 이용해 풀어보았다.
플로이드-와샬 알고리즘은 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘이지만, 이 문제에서는 양수인 경로의 존재 여부를 판별하기 위해 활용된다.
플로이드-와샬 알고리즘을 적용하기 위해 삼중 중첩 반복문을 사용합니다.
먼저, 3중 중첩된 반복문에서 k는 거쳐가는 노드를 나타내고, i와 j는 시작 노드와 도착 노드를 나타낸다.
for문안에 중간 노드를 거쳐가는 경로를 검사하여 양수인 경로가 있는지 확인하였다.
결과적으로 인접 행렬의 각 원소 (i, j)가 1이면 i에서 j로 가는 양수인 경로가 있음을 의미하고, 0이면 양수인 경로가 없음을 의미함.
간단히 설명하면, 모든 노드 쌍 간의 최단 경로를 찾기 위해 중간에 거쳐가는 노드(k)를 활용하는 방식이다.
graph[i][k]와 graph[k][j]가 둘 다 1이면, 즉 노드 i에서 노드 k로 가는 간선과 노드 k에서 노드 j로 가는 간선이 존재하면, 노드 i에서 노드 j로 가는 간선을 연결해준다.
말로 풀어서 생각해보면 시작이나 끝을 기준으로 먼저 연결하는 게 아니고
중간다리를 기준으로 미리미리 연결해둬야 나중에 한번에 따닥 연결이 된다
이를 통해 중간에 거쳐가는 노드를 활용하여 최단 경로를 갱신한다.
모든 노드 쌍에 대해 이러한 과정을 반복하면, 최종적으로 graph는 모든 노드 쌍 간의 최단 경로 정보를 담게 됩니다.
마지막으로, 갱신된 graph를 출력하여 최단 경로 정보를 확인하면 된다.
풀이코드
import sys
N = int(sys.stdin.readline())
graph = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
for k in range(N):
for i in range(N):
for j in range(N):
if graph[i][k] and graph[k][j]:
graph[i][j] = 1
for g in graph:
for e in g:
print(e, end=" ")
print()