Problem Solving/DFS, BFS

[DFS, BFS] 백준 11403번: 경로 찾기

by ggyongi 2021. 5. 29.

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

www.acmicpc.net

import collections
n = int(input())
graph = collections.defaultdict(list)

for i in range(n):
    edges = list(map(int, input().split()))
    for j in range(len(edges)):
        if edges[j] == 1:
            graph[i].append(j)

def dfs(node):
    if node in discovered:
        return
    discovered.append(node)
    for next in graph[node]:
        dfs(next)

for i in range(n):
    discovered = []
    for j in graph[i]:
        dfs(j)
    answer = [0]*n
    for j in range(len(discovered)):
        answer[discovered[j]] = 1
    print(*answer)

쉬운 dfs 문제!