[SWEA][D4][#01219] 길찾기

출처

• SW Expert Academy

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

문제

그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다.

길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다.

다음과 같이 길이 주어질 때, A도시에서 B도시로 가는 길이 존재하는지 알아내는 프로그램을 작성하여라.

• A와 B는 숫자 0과 99으로 고정된다.

• 모든 길은 순서쌍으로 나타내어진다. 위 예시에서 2번에서 출발 할 수 있는 길의 표현은 (2, 5), (2, 9)로 나타낼 수 있다.

• 가는 길의 개수와 상관없이 한가지 길이라도 존재한다면 길이 존재하는 것이다.

• 단 화살표 방향을 거슬러 돌아갈 수는 없다.

제약사항

출발점은 0, 도착점은 99으로 표현된다.

정점(분기점)의 개수는 98개(출발점과 도착점 제외)를 넘어가지 않으며, 한 개의 정점에서 선택할 수 있는 길의 개수도 2개를 넘어가지 않는다.

아래 제시된 가이드 라인은 제안사항일 뿐 강제사항은 아니다.

입력

각 테스트 케이스의 첫 줄에는 테스트 케이스의 번호와 길의 총 개수가 주어지고 그 다음 줄에는 순서쌍이 주어진다.

순서쌍의 경우, 별도로 나누어 표현되는 것이 아니라 숫자의 나열이며, 나열된 순서대로 순서쌍을 이룬다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다.

예제

입력

1 16
0 1 0 2 1 4 1 3 4 8 4 3 2 9 2 5 5 6 5 7 7 99 7 9 9 8 9 10 6 10 3 7
2 159
0 4 0 10 1 4 1 10 2 11 2 8 3 13 4 8 4 11 5 10 5 8 6 10 6 11 7 8 7 15 8 14 9 10 9 20 10 14 10 17 11 21 12 21 13 14 13 17 14 20 15 22 16 22 16 20 17 19 18 28 18 29 19 27 20 29 21 31 21 30 22 24 22 30 23 24 23 26 24 27 25 31 26 31 26 37 27 34 27 30 28 38 28 30 29 32 30 38 30 32 31 35 31 36 32 34 32 37 33 40 33 44 34 44 35 39 35 46 36 38 36 41 37 40 38 40 38 49 39 41 39 44 40 45 41 44 41 50 42 44 42 51 43 45 43 52 44 45 44 52 45 48 45 52 46 47 46 55 47 48 47 58 48 53 49 55 50 59 50 60 51 57 51 60 52 60 52 63 53 57 53 62 54 62 54 65 55 62 56 58 57 66 58 64 58 61 59 69 60 62 61 63 62 68 62 64 63 66 64 68 64 71 65 75 65 67 66 75 66 73 67 71 67 72 68 72 68 70 69 72 70 71 70 80 71 80 72 81 72 83 73 77 73 75 74 83 74 78 75 81 75 85 76 79 76 82 77 86 77 87 78 86 78 81 79 89 80 84 80 86 81 83 81 88 82 87 82 86 83 86 83 94 84 94 84 88 85 95 86 91 86 97 87 93 88 92 88 90 89 97 89 92 90 99 91 95 92 96 92 97 94 95 95 97 95 99 96 97
........

출력

#1 1
#2 1
.......

My Sol

def func(s, e, path):
    global node
    if s==e:
        return 1
    elif node[s]==[]:
        return 0

    p_lst = node[s]
    for p in p_lst:
        if p in path:
            continue
        if func(p, e, path+[p]):
            return 1
    return 0

for _ in range(10):
    node = [[] for _ in range(100)]
    path = [0]
    tc, N = map(int, input().split())
    nums = list(map(int, input().split()))
    for i in range(N):
        node[nums[i*2]] += [nums[i*2+1]]

    print(f'#{tc} {func(0, 99, path)}')

숫자를 공백을 기준으로 입력받아서 짝수 인덱스는 node의 인덱스로 쓰고, 홀수 인덱스는 도착 노드의 숫자로 사용하였다. 처음에 빈 리스트로 0부터 99까지 정의해준 node 배열에 출발 노드를 인덱스로 하는 리스트 원소에 도착 노드 번호를 입력해 넣는 것이다. 이를 func() 함수에서 사용한다.

func()함수는 DFS로 도착 노드의 도착 노드의 도착 노드로 이동하며 s와 e가 같은 순간에 1을 return하는 재귀함수를 작성하였다. 출발 노드의 번호에 해당하는 인덱스의 node 항목이 도착 노드가 없는 빈 리스트 항목인 경우 바로 0을 return하게 하였고, 무한 루프를 돌지 않도록 path 배열을 따로 인자로 지정하여 도착 노드로 이동할 때마다 path에 출발 노드를 넣어주었다. 만약 해당 노드의 도착 노드가 출발점부터 해당 노드까지 밟아온 노드 경로에 있는 노드라면 무한 루프를 돌 것이기 때문에 이를 판단하여 해당하면 0을 return해준다.

결과

PASS

모범답안

def my_dfs(start, end, graph):
    visit = []
    stack = []
    stack.append(start)
    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(graph[node])

    if end in visit:
        return 1
    else:
        return 0

for tc in range(1,11):
    t, line = map(int,input().split())
    arr = list(map(int,input().split()))

    graph = [[] for _ in range(101)]
    for l in range(0,len(arr),2):
        graph[arr[l]].append(arr[l+1])

    print(f'#{tc}',my_dfs(0, 99, graph))

양해를 구하고 동기의 코드를 참조하였다. visit이라는 배열을 만들었고, 경로를 의미하는 stack도 사용하였다. 내 코드에서 path와 같은 역할을 한다. graph라는 배열에 출발 노드 번호를 인덱스로 하는 도착 노드 리스트를 원소로 하고, 이를 함수에 인자로 넣어주었다. 뭐 global로 써도 되고 인자로 넣어도 된다.

함수 내부에서 stack을 정의하고 출발 노드를 append 해준다. 스택이 빈 리스트가 아닌동안, while문을 반복하는데, stack을 pop한 것을 node라고 지정하는데, 만약 visit에 node가 있다면 조회하지 않고 다시 stack에서 pop하고, visit에 node가 없다면 가지 않은 노드이므로 visit.append(node)로 방문 노드 리스트에 넣어주고, stack에는 graph[node], 즉 node를 출발 노드로 하여 도착할 수 있는 도착 노드를 extend한다. 리스트를 벗겨 번호로만 저장하는 것.

이후 stack이 다시 차면 도착 노드들을 재료로 하여 방문하지 않은 노드들에 대해 도착하는 것을 반복한다. 따지면 재귀가 아닌 것이다. 그렇기 때문에 실행속도가 빠른 것 같기도 하다. 함수의 호출이 반복되지 않기 때문..

def func(nodes, start, end):
    stack = []
    visit = []

    stack.extend(nodes[start])
    while stack:
        t = stack.pop()

        if t not in visit:
            visit.append(t)
            stack.extend(nodes[t])

        if end in visit:
            return 1
    return 0

for _ in range(10):
    tc, N = map(int, input().split())
    arr = list(map(int, input().split()))
    nodes = [[] for _ in range(100)]

    for i in range(N):
        nodes[arr[i*2]] += [arr[i*2+1]]

    print(f'#{tc} {func(nodes, 0, 99)}')

거의 일치하지만 나도 완전히 익히기 위해서 흐름만 익히고 내가 완전히 새로 짜보았다. 좋은 방식인 것 같다.