[baekjoon] 백준 11403번(파이썬): 경로 찾기

문제

11403번: 경로 찾기

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

알고리즘

- dfs 탐색을 통해 문제를 수행한다.

- n번을 반복하는 동안 체크 리스트를 계속해서 초기화하여 dfs 탐색을 한다.

- dfs는 한줄씩 비교하여 재귀적으로 탐색한다.

코드

import sys


# dfs 탐색
def dfs(v):
    # 한줄씩 비교
    for i in range(n):
        if check[i] == 0 and graph[v][i] == 1:
            check[i] = 1
            dfs(i)


n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

for x in range(n):
    # 체크 리스트를 초기화하여 수행
    check = [0 for _ in range(n)]
    dfs(x)
    print(*check) # 리스트의 경우에는 *기호를 넣어서 각각의 값을 출력할 수 있다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법