SWEA - 그래프 경로 (4871) [Python]

 문제

 

노드들이 주어질 때 출발점에서 목표로 도달할 경로가 존재하면 1을 출력, 없으면 0을 출력한다.

 

 

 문제 상황

 

- 단방향 연결이며 depth를 찾는게 아니라 경로의 존재여부를 탐색하는 것이기 때문에 쉬운 문제다.

 

 

 해결 전략

 

- DFS / BFS 모두 활용 가능하지만 직관적인 DFS를 활용하기 위해 스택을 사용하였다.

 

 

 코드

 

# testcase 개수
T = int(input())
for idx in range(T):
    # v = 노드의 수, e = 연결의 수
    v, e = map(int, input().split())
    # 연결 상태를 보여준다.
    adj = [[] for _ in range(v+1)]
    # 방향이 있는 노드이므로 adj[출발] = [도착] 으로 정의해준다.
    for _ in range(e):
        start, end = map(int, input().split())
        adj[start].append(end)
    from_node, to_node = map(int, input().split())
    # 가능한 길이 있는지 여부를 확인
    is_Check = False
    # DFS를 활용하기위해 stack을 설정하고 시작점을 넣는다.
    stack = [from_node]
    # 특정 연결이 양방향 노드일 수도 있기 때문에 방문 여부를 체크하는 리스트를 만든다.
    check_list = [False] * (v+1)
    while stack :
        # stack의 최상단 값을 꺼낸다.
        check_node = stack.pop()
        # 꺼낸 값이 목표와 같다면 도달할 방법이 있으므로 반복을 종료
        if check_node == to_node:
            is_Check = True
            break
        # 꺼낸 값이 목표와 다를 때 아직 방문하지 않은 노드라면 노드와 연결된 점들을 stack에 넣어준다.
        elif not check_list[check_node]:
            stack.extend(adj[check_node])
        # 방문했다는 표시를 해준다.
        check_list[check_node] = True
    # 경로가 존재하면 1을 출력
    if is_Check :
        print(f"#{idx+1} 1")
    # 존재하지 않으면 0 출력
    else:
        print(f"#{idx+1} 0")
        
        

 

 

 해설

 

- 단순히 경로 존재 여부였으므로 간단한 반복문으로 구현 가능했다. 만약 depth를 찾아야 한다면 함수를 하나 새로 지정해서 recursive를 사용했을 것 같다.

 

 

 새로 학습한 것 & 실수 

 

- .

 

 

출처 - https://swexpertacademy.com/main/