[Silver I] 경로 찾기 - 11403

문제 링크

성능 요약

메모리: 34036 KB, 시간: 72 ms

분류

플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로

제출 일자

2024년 11월 14일 22:05:23

문제 설명

가중치 없는 방향 그래프 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으로 출력해야 한다.

풀이

n = int(input())
graph = [[i for i in map(int, input().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:
     print(*g)

이 문제 풀이의 알고리즘으로는 플로이드 워셜 알고리즘을 사용해야 한다고 한다.

이 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다.

조금 더 구체적인 설명을 위해, 임의의 노드 s 부터 e 까지 가는데 걸리는 최단거리를 d[s][e]라고 하자. (처음에 d[s][e]의 값은 노드 s와 노드 e가 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)로 초기화한다.[3]) 이 d[s][e]를 구하기 위해서, s와 e 사이의 모든 노드 m에 대해, 현재 d[s][e]에 저장되어 있는 값과, d[s][m]+d[m][e]의 값을 비교한다. 이 때 d[s][m]+d[m][e]의 값이 현재의 d[s][e] 값보다 작으면, d[s][e]를 d[s][m]+d[m][e] 의 값으로 업데이트한다.

노트북 터치패드로 그려 그림이 이상하지만.. 이 그림은 입력 값에 나온 것을 그림으로 그린 것이다.

결과 값을 보면 (0, 0)을 보면 1로 되어 있다. 이는 `0 -> 3 -> 4 -> 0`으로 갈 수가 있다.

이와 같이 모든 결과를 진행해야 하기 때문에 (0, 0)으로 가기 위해 중간 노드들에 간선이 있다면 (0, 0)에도 간선이 존재하다는 것을 알 수 가 있기에 플로이드 워셜 알고리즘을 활용하면 된다.

또한 이는 BFS나 DFS와 같은 알고리즘으로 해결할 수 있을 것 같아. BFS로 해결도 해봤다.

from collections import deque

n = int(input())
graph = [[i for i in map(int, input().split())] for _ in range(n)]

def bfs(x):
    queue = deque([x])
    check = [False for _ in range(n)]
    while queue:
        v = queue.popleft()
        for i in range(n):
            if not check[i] and graph[v][i]:
                queue.append(i)
                check[i] = True
                graph[x][i] = 1
                
for i in range(n):
    bfs(i)
    
for g in graph:
    print(*g)

0부터 n까지 bfs를 다 돌아줘야 한다.

bfs함수에서 for문으로 0부터 n까지 돌아주는 이유는 현재 노드가 0부터 6까지 갈 수 있는지를 돌면서 확인을 해야 하기 때문이다.

예를 들면 먼저 0으로 시작되면 0에서 0으로 가는 간선이 있고 방문한 적이 없다면 큐에 넣고 방문처리를 해준다. 방문처리는 bfs를 돌 때마다 초기화를 해줘야 한다.