[Python] SW Expert Academy - 4871. 그래프 경로

SW Expert Academy 4871번 그래프 경로 문제는 V개 이내의 노드를 E개의 간선으로 연결한 방향성 그래프에 대한 정보가 주어질 때, 특정한 두 개의 노드에 경로가 존재하는지 확인하여 존재 여부를 출력하는 문제이다. 스택 자료구조에 관한 문제로 난이도는 D2이다.

 

SW Expert Academy 4871번 그래프 경로 문제 정보

자료구조 분류

- 스택 Stack

난이도

- D2

 

그래프 경로 문제 요약

• V개 이내의 노드를 E개의 간선으로 연결한 방향성 그래프에 대한 정보가 주어진다.
• V의 범위는 5 이상 50 이하, E의 범위는 4 이상 1000 이하이다.
• 노드 번호는 1번부터 존재하며, 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.
• E개의 줄에 걸쳐 출발 노드, 도착 노드로 간선 정보가 주어진다.
• 경로의 존재를 확인할 출발 노드 S와 도착 노드 G가 주어진다.
• S, G 노드에 대해 경로가 있으면 1, 없으면 0을 출력한다.

문제 풀이 과정

1. 노드별 연결된 노드 번호를 저장하는 2차원 리스트 node를 정의한다.
2. 시작 노드를 스택에 push 하고 방문으로 바꾼다.
3. 스택이 비어있지 않을 동안, 현재 노드가 도착 노드이면 경로가 존재하므로 1을 리턴한다.
4. 현재 노드가 도착 노드가 아니면
   • 현재 노드와 연결된 노드들 중 방문 안 한 노드들을 방문하고 스택에 저장한다.
   • 마지막으로 방문한 노드를 현재 노드에 저장하고 스택에서 pop 한다.
5. 스택이 빈다면 경로가 존재하지 않으므로 0을 리턴한다.
6. 테스트 케이스 번호, 경로 존재 여부를 출력한다.

코드 및 설명

• node [][] - index: 노드 번호, value: 연결된 노드 번호들을 저장한 2차원 리스트
• visited [] - 노드 별 방문 정보 (방문=1, 미방문=0)
• stack [] - 경로에 따라 방문 중인 노드들을 저장한 스택

def search_path(node_num, goal):
    stack.append(node_num)
    visited[node_num] = 1
    while stack:
        if node_num == goal:
            return 1
        else:
            for i in node[node_num]:
                if not visited[i]:
                    visited[i] = 1
                    stack.append(i)
            node_num = stack.pop()
    return 0

for t in range(int(input())):
    V, E = map(int, input().split())
    node = [[] for _ in range(V+1)]
    visited = [0]*(V+1)
    stack = []
    for _ in range(E):
        start, end = map(int, input().split())
        node[start].append(end)
    S, G = map(int, input().split())
    
    print("#%d %d"%(t+1, search_path(S, G)))

---

SW Expert Academy 4871번 그래프 경로 문제는 스택 자료구조를 이용해 그래프의 노드들을 탐색하여 경로의 존재를 묻는 문제이며 파이썬을 사용하였다. 난이도는 D2인데, 해결 법이 쉽게 생각나지 않아서 어려웠고 다음에 다시 풀어봐야겠다.