11403-경로 찾기

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

11403번: 경로 찾기

간단한 그래프 탐색 문제. 알고리즘 분류에는 플로이드-와샬 이 포함되어 있는데, 간선 사이 가중치가 없고 i에서 j로 가는 경로가 있는지만 체크하면 되는 문제라 일반적인 DFS로 해결하였다.

인접행렬 형태로 받은 간선 정보를 이용하여 간선이 존재하는 기본 좌표를 [start, now] 형태로 stack에 넣어놓고  stack에서 하나씩 pop해 가며 DFS를 수행한다.

 

문제를 풀어보면서 아직 BFS보다 DFS 구현이 조금 낯선 느낌이 들었다. 당분간 DFS를 이용한 그래프 탐색 문제를 조금 더 풀어봐야겠다.

 

N = int(input())
arr = [list(map(int, input().split()))for _ in range(N)] 
ans = [[0]*N for _ in range(N)] 


stack = []
for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            ans[i][j] = 1
            stack.append([i,j])
    while stack:
        start, now = stack.pop()
        for nxt in range(N):
            if ans[start][nxt] == 0 and arr[now][nxt] == 1:
                ans[start][nxt] =1
                stack.append([start, nxt])
        
for i in range(N):
    for j in range(N):
        print(ans[i][j], end=' ')
    print()