SWEA 4871 그래프 경로 DFS (파이썬)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

[SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com](https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do)

 

---

문제

V개 이내의 노드를 E개의 간선으로 연결한 방향성 그래프에 대한 정보가 주어질 때, 특정한 두 개의 노드에 경로가 존재하는지 확인하는 프로그램을 만드시오.

두 개의 노드에 대해 경로가 있으면 1, 없으면 0을 출력한다.

예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경로를 찾는 경우, 경로가 존재하므로 1을 출력한다.
 

 

노드번호는 1번부터 존재하며, V개의 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.

 
 

[입력]
 

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50
 

다음 줄부터 테스트 케이스의 첫 줄에 V와 E가 주어진다. 5≤V≤50, 4≤E≤1000
 

테스트케이스의 둘째 줄부터 E개의 줄에 걸쳐, 출발 도착 노드로 간선 정보가 주어진다.
 

E개의 줄 이후에는 경로의 존재를 확인할 출발 노드 S와 도착노드 G가 주어진다.

 

[출력]
 

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

---

풀이 및 해설(주석)

def dfs(v):                 # dfs 함수 선언
    visited[v] = 1          # visited에 다녀간 흔적을 1으로 남겨둠
    for w in G[v]:          # v에 연결된 값들을 반복문으로 돌림
        if visited[w] == 0: # w에 방문하지 않았다면
            dfs(w)          # 재귀
# 재귀가 다 되면(함수가 끝나면) visited에는 지나온 흔적이 남겨져 있을 것이다.


for tc in range(int(input())):
    V, E = map(int, input().split())     # V개의 노드, E개의 간선
    G = [[] for _ in range(V + 1)]       # 노드의 수 만큼 인접리스트를 생성
    for _ in range(E):
        u, v = map(int, input().split()) # u정점의 인접 정점 v
        G[u].append(v)                   # 인접리스트에 넣어줌, 간선이 아니라면 G[v].append(u)도 해줘야됨
    s, g = map(int, input().split())     # 시작 정점, 도착 정점
    visited = [0] * 51
    dfs(s)
    if visited[g] == 1:                  # 도착 정점이 visited에 기록되어 있다면
        print(f'#{tc+1}', 1)             # 1을 출력
    else:
        print(f'#{tc+1}', 0)

 

---

후기

DFS를 이용하여 각 노드의 간선에 대해 탐색하는 함수를 만들어 사용했다.

정말 기초적인 DFS탐색이라 간단한 재귀함수를 만들어 visited에 방문한 기록을 표시하게 만들었다.

DFS와 재귀가 섞여 있지만 이런 문제라면 간단하게 접근 가능하다.

앞으로 DFS와 재귀를 더 깊게 배울 예정인데, 잘할 수 있을지 걱정이 많이 된다..