11403 - 경로 찾기

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

11403번: 경로 찾기

 

 

- 그래프 탐색

 

import sys
input = sys.stdin.readline

def search(x):
    if path_v:
        visited[x] = True
    path_v.append(x)
    for i in range(n):
        if visited[i] == False and matrix[x][i] == 1:
            search(i)


n = int(input())

matrix = list()
for _ in range(n):
    matrix.append(list(map(int, input().split())))

path = list()
for v in range(n):
    path_v = list()
    visited = [False] * n

    search(v)
    path_v.remove(v)
    path.append(path_v)

for i in path:
    ans = [0] * n
    for j in i:
        ans[j] += 1
    
    for k in range(n):
        if ans[k] == 1:
            print(1, end=' ')
        else:
            print(0, end=' ')
    print()

 

DFS로 재귀를 사용해서 구현했다! 근데 노트처럼 visited 리스트 값을 바로 True로 바꿔버리면 Cycle을 형성하는지 알 수 없어서 path_v 안에 값이 있어야만 (즉, 처음 search가 시작한 것이 아닐 때만) visited를 참으로 바꿔줬다

 

BFS보단 DFS가 구현하기도 편하고 알아보기도 쉬워서 자주 사용하는 것 같다 ㅎ... 나중에 BFS로도 탐색 문제를 풀어봐야게따 (안할 가능성 다분)