백준 11403번 : 경로 찾기 in Python

11403번: 경로 찾기

 

www.acmicpc.net

이 문제는 방향 그래프가 인접행렬 형식으로 주어졌을 때 모든 정점 쌍 (i, j)에 대해 i에서 j로 가는 경로가 있는지 없는지를 구하는 문제이다.

만약 주어진 그래프가 방향이 없는 간선만 주어졌다면 disjoint set operation을 이용해 임의의 두 정점 쌍이 연결되어 있는지를 쉽게 확인할 수 있다. 하지만 이 문제는 방향이 있는 간선이 주어지는 경우이므로 그래프 탐색을 통해 임의의 점과 연결된 모든 점을 찾는 방식으로 문제를 해결해야 한다.

여기서 주의해야 할 점은 임의의 점과 연결된 점을 찾을 때 자기 자신을 포함하는 경우는 자신을 포함하는 사이클이 있는 경우뿐이라는 점이다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
mat = []
for _ in range(N):
    mat.append(list(map(int, input().split())))
for i in range(N):
    for j in range(N):
        if mat[i][j] == 1:
            graph[i].append(j)
# 결과를 저장할 행렬
res = [[0]*N for _ in range(N)]
for i in range(N):
    queue = deque()
    queue.append(i)
    visited = [False for _ in range(N)]
    while len(queue) > 0:
        u = queue.popleft()
        if visited[u]: continue
        visited[u] = True
        for v in graph[u]:
            queue.append(v)
            # 해당 점과 연결된 점들을 반영한다.
            res[i][v] = 1
for i in range(N):
    print(" ".join(map(str, res[i])))