문제 출처 : [SWEA] 4871 그래프 경로
learn -> course -> programming intermediate -> stack1 -> 그래프 경로

문제

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

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

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

입력

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

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

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

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

출력

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

코드

# 노드 간 연결을 확인하는 함수
def dfs(start, goal):
    visited[start] = 1  # 방문한 노드는 1로 변경

    for i in range(1, V + 1):
        # 이동 가능한 노드가 존재하고 그 노드를 방문하지 않았을 경우 재귀함수 호출
        if graph_list[start][i] == 1 and visited[i] == 0:
            dfs(i, goal)
        # 도착지를 방문했다면 return 1
        if visited[goal]:
            return 1
    return 0


T = int(input())
for tc in range(1, T + 1):
    V, E = map(int, input().split())  # 노드 수, 간선 수
    graph_list = [[0] * (V + 1) for _ in range(V + 1)]  # 인접 행렬을 저장할 2차원 리스트
    visited = [0] * (V + 1)  # 해당 노드를 방문했는지 여부를 저장할 리스트

    # 노드의 수만큼 반복하면서 리스트에 저장
    for i in range(E):
        a, b = map(int, input().split())
        graph_list[a][b] = 1

    # 시작 노드와 끝 노드를 받아옴
    s, g = map(int, input().split())

    # 함수 호출하여 출력
    print('#{} {}'.format(tc, dfs(s, g)))

풀이 방법

우선 노드들을 인접행렬에 저장해서 활용하였다. dfs를 활용해서 방문한 노드는 방문처리를 해주고 이동 가능한 노드가 있다면 다음 노드를 함수에 넣어서 계속 호출하는 방식으로 코드를 작성하였다. 그렇게 해서 마지막에 도착지점에 방문처리가 됐을 경우 1을 return 해주었다. 아직 재귀함수로 코드를 작성하는 것이 익숙하지 않아서 더 연습을 해야할 것 같다.