[SWEA][D3][#04871] 그래프 경로

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예제

입력

3
6 5
1 4
1 3
2 3
2 5
4 6
1 6
7 4
1 6
2 3
2 6
3 5
2 5
9 9
2 6
4 7
5 7
1 5
2 9
3 9
4 8
5 3
7 8
1 9

출력

#1 1
#2 1
#3 1

My Sol

def dfs(arr, s, e, lst):
    if s == e:
        return 1
    elif arr[s] == []:
        return 0

    for p in arr[s]:
        for k in lst:
            if k == p:
                return 0

        if dfs(arr, p, e, lst + [p]):
            return 1
    return 0

T = int(input())
for tc in range(1, T+1):
    V, E = map(int, input().split())
    arr = [[] for _ in range(V+1)]
    for _ in range(E):
        a, b = map(int, input().split())
        arr[a] += [b]

    s, e = map(int, input().split())
    print(f'#{tc} {dfs(arr, s, e, [s])}')

먼저 노드의 번호와 인덱스를 일치하게 하기 위해서 노드의 개수인 V보다 1개 더 많게 arr를 초기화해주었다. 노드 번호와 같은 인덱스에 도착 노드의 번호를 항목으로 넣기 위해 빈 리스트와 함께 초기화하였다. 그리고 E개의 출발-도착 노드 입력을 처리하기 위해 for문을 사용하여 출발 노드를 a, 도착 노드를 b로 처리하였다. 그리고 arr의 초기화 목적처럼 arr[a]에 b를 추가해주며 입력을 처리하였다.

이렇게 입력이 모두 처리된 상태에서 확인하고자 하는 출발-도착 노드 입력을 처리하여 s, e에 할당하였다. 이후에는 s와 e, arr를 이용하는 함수 dfs()를 정의하여 여부를 반환하였다.

dfs함수는 재귀함수인데, 출발 노드와 도착 노드를 인자로 받는다. 만약 재귀의 base condition, 즉 종료 조건으로는 s == e, 즉 특정 노드의 도착 노드에 최초 목적 노드가 있다면 1을 반환하며 종료하도록 하였다. 혹은 arr[s]가 빈 리스트, 즉 어디로도 가지 않는 노드의 끝이라면 0을 반환하며 끝낸다.

그 외, 즉 입력으로 들어온 시작 노드를 인덱스로 하는 arr[s]가 항목을 가지고 있는 리스트라면 항목 각각을 p로 두어 lst의 k와 각각 비교한다. 자. 이 lst는 무엇인가. lst는 함수에 argument로 처음부터 입력되어 parameter로 전달되는 인자인데, 노드의 이동 경로를 나타내기 위해 사용하였다. 이것이 없다면 함수는 이전 노드와 현재 노드만 알고 있는 상태가 되기 때문에 얼마를 돌고 돌아 다시 처음의 출발 노드 또는 경로 상에 있는 노드에 도달해 무한 루프를 돌게 될 수도 있다.

때문에 어떤 노드에서 다른 노드로 출발할 때 출발하는 노드를 리스트에 저장하여 인자로 전달하는 것이다. 그러면 p를 lst상에서 조회해서 경로에 p가 있다면 또 가봐야 다시 무한루프를 돌 것이므로 return 0으로 끊어주는 것이다.

만약 p가 lst에도 없는, 즉 새로운 경로의 도착 노드라면 도착 노드를 다시 출발 노드로 하는 dfs 함수를 호출해주면 되겠다. 물론 lst에는 출발노드인 p를 추가하기 위해 lst + [p]로 인자로 전달한다. 재귀 함수가 경로를 파고 파다가 어느 출발 노드의 도착 노드가 목표 노드인 e와 일치한다면 1을 호출해 그를 호출한 곳으로 다시 올라가고 올라갈텐데, 그러면 if dfs(arr, p, e, lst + [p]) 가 1, True가 되고 최초에 호출한 위치에서도 1을 반환한다.

이를 출력 형식에 맞춰 출력하면 되겠다.

결과

PASS