[백준] 11403번 경로 찾기

Yeon·2023년 8월 30일

DFS 백준 파이썬

백준

목록 보기

5/6

[Silver I] 경로 찾기 - 11403

문제 링크

성능 요약

메모리: 31388 KB, 시간: 1088 ms

분류

플로이드–워셜, 그래프 이론, 그래프 탐색

문제 설명

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

🔧 알고리즘

입력에서 주어진 adjacent matrix를 통해서 직접 어떤 노드가 다른 노드를 향해가고 있는 지를 튜플로 만들어준다. 이제 이것을 튜플로 만들었으면 list를 정점의 갯수만큼 이차원리스트를 만들어준다. 그 후에 튜플을 하나씩 읽어가면서 0번째 위치한 값은 시작, 1번째 위치한 값은 도착이라고 가정하고 각 시작 값을 기준으로 리스트에 도착 값을 추가해준다. 말로 표현하기 어려워서 추가적인 설명은 밑에서 자세히 할 예정이다. 그 후 DFS를 통해서 문제를 푸는 방식이다.

코드 설명

adjacent matrix를 입력 받고, 그 중 값이 1인 것들만 tuple 형태로 (시작, 도착) 이런 노드로 저장하는 코드이다

N = int(input())

adj_mat = [input().split() for _ in range(N)]

new_adj_mat = []

for i in range(N) :
    for j, k in enumerate(adj_mat[i]) :
        if k == '1' :
            new_adj_mat.append((i,j))

N개의 갯수만큼의 이차원 리스트를 만들어준다. 그리고 그 이차원리스트에 튜플을 하나씩 읽으면서 시작하는 node의 리스트 번호에 도착하는 node를 append 시켜준다. 이렇게 되면 각 node가 어떤 node를 가리키고 있는 지 쉽게 볼 수 있다.
```
final_adj_mat = [[] for _ in range(N)]
for one in new_adj_mat :
   final_adj_mat[one[0]].append(one[1])
```
가장 주된 핵심 알고리즘 DFS
```
def stack_graph(N, final_adj_mat, result) :
   for k in range(N) :
       stack = [k]
       vst_vert = []
       while stack :
           current = stack.pop()
           for neighbor in final_adj_mat[current] :
               result[k][neighbor] = 1
               if neighbor not in vst_vert :
                   stack.append(neighbor)
           
           vst_vert.append(current)
   
   return result
```
위에서 우리가 만들었던 2차원 리스트를 파라미터로 넣는다. DFS의 주된 핵심은 stack을 사용한다는 것이다. 우리는 현재 0 ~ N-1번째 각각에서 구하고 싶기 때문에 0 ~ N-1번째 까지 반복문을 사용한다. stack에 들어가는 첫번째 원소는 시작하는 node를 기본으로 세팅해준다. 그리고 vst_vert는 쉽게 말해서 방문했던 노드를 집어 넣는 것이다. 반복문을 사용해서 더이상 stack에 값이 없게 되면 반복문이 종료되는 것이다. final_adj_mat[current]가 가리키고 있는 node를 하나씩 꺼내와서 그 값은 1로 바꿔주는 것이다. 왜냐하면 양수인 경로이기 때문이다. 그리고 만약에 vst_vert에 들어가 있지 않는 값이면 stack에 append 해준다. 해당 반복문이 종료되고 나면 vst_vert에도 current를 append 해준다.
결과