[맛있는물회] <SWEA알고리즘> 4871번 "그래프 경로"

문제 조건

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

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

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

 

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

---

 

 

Input

---

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

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

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

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

 

Output

---

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

 

생각한 아이디어

---

먼저 입력값에 맞추어 그래프를 그려야한다. 그래프를 그리는 방법은 여러가지가 있다.

Adjacency Graph를 배열로 그리거나, 포인터를 사용해서 그리거나,,

여기서 나는 파이썬의 Dictionary 개념과 set 개념을 사용하여 인접리스트를 그려보았다.

 

Edge들을 입력받기전 Vertex와 Edge의 개수를 안다.

Vertex의 개수만큼 딕셔너리를 생성한다.

Edge가 입력되면 해당하는 딕셔너리를 찾고 그의 value 값에 연결되는 vertex 번호를 저장한다.

이렇게 adj라는 딕셔너리에 인접리스트가 저장되었다.

#    undirected graph

#    graph = {'A': set(['B', 'C']),

#       'B': set(['A', 'D', 'E']),

#       'C': set(['A', 'F']),

#       'D': set(['B']),

#       'E': set(['B', 'F']),

#       'F': set(['C', 'E'])}

 

그 후 Start에서 End의 경로를 확인하기 위해 DFS를 사용하였다.

DFS와 BFS에 대한 내용은 다음에 다시 한번 정리를 해야할 필요가 있다.

 

DFS를 통해 Visit 한 Vertex들이 나오면 그 중 End 값이 있는지 확인 후 경로의 유무를 결정한다.

 

 

 

소스코드

def dfs(graph, start, end):
    visited = list()
    stk = list()
    stk.append(start)
    while stk:
        node = stk.pop()
        if node not in visited:
            visited.append(node)
            stk += graph[node] - set(visited)
    #print(visited)
    if end in visited:
        return 1
    else :
        return 0

T = int(input())

for TC in range(1, T + 1):
    V, E = map(int, input().split())
    adj = {1:set([])}
    for j in range(2,V+1):  #vertex 개수만큼 딕셔너리 추가
        adj[j] = set([])
#    undirected graph
#    graph = {'A': set(['B', 'C']),
#       'B': set(['A', 'D', 'E']),
#       'C': set(['A', 'F']),
#       'D': set(['B']),
#       'E': set(['B', 'F']),
#       'F': set(['C', 'E'])}
    
    for i in range(E): 
        start, end = map(int,input().split())
        adj[start].add(end)

    A,B = map(int, input().split())
    print("#%d %d" %(TC, dfs(adj, A, B)))

 

*파이썬 문법 정리

- def로 함수를 정의한다.

- 배열을 단순하게 return 할 수 있어서 아주 간편하다.

- 그래프를 그릴때 C에서 해야하는 구조체를 만드는 작업을 할 필요가 없고 Dictionary로 작업이 가능하다.