[알고리즘 문제 풀이] 길찾기

📍  문제 요약

그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다.
길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다.
다음과 같이 길이 주어질 때, A도시에서 B도시로 가는 길이 존재하는지 알아내는 프로그램을 작성하여라.
 - A와 B는 숫자 0과 99으로 고정된다.
 - 모든 길은 순서쌍으로 나타내어진다. 위 예시에서 2번에서 출발 할 수 있는 길의 표현은 (2, 5), (2, 9)로 나타낼 수 있다.
 - 가는 길의 개수와 상관없이 한가지 길이라도 존재한다면 길이 존재하는 것이다.
 - 단 화살표 방향을 거슬러 돌아갈 수는 없다.

 

 

 

💡 소스 코드

# 0번 정점에서 시작해서 99번에 도착할 수 있으면, 1 아니면 0을 반환하는 함수
# dfs 수행하면서 99번 정점에 도착하면 1 반환
def dfs():
    start, end = 0, 99
    # 경로 저장을 위해서 stack 만들기
    stack = [start]
    # 재방문 방지를 위해서 visited 만들기
    visited = [0] * 100
    visited[start] = 1
    # stack의 마지막 요소가 현재 위치
    # 현재 위치에서 갈 수 있는 정점 찾으면서
    # 갈 수 있는 정점이 있으면 경로에 추가, 없으면 현재 정점 제거
    while stack:
        current = stack[-1]
        if current == end:  # 현재 위치가 찾는 목적지라면
            return 1  # 1반환
        # 아직 목적지가 아니라면 길찾기 계속하기
        # 현재 정점과 연결된 정점 보기 >> graph[0][current], 와 graph[1][current] 을 보면 된다.
        for i in range(2):
            v = graph[i][current]  # 방문하려는 정점번호
            if v != -1 and not visited[v]:  # 정점에 방문하지 않았으면 방문
                stack.append(v)
                visited[v] = 1
                break
        else:  # 현재 정점에서 갈 수 있는 길이 없으면?
            # 현재 정점을 경로상에서 제거
            stack.pop()
    # while 문 끝나고 나서 목적지에 도달할 수 없으면
    return 0


for _ in range(10):
    tc, E = map(int, input().split())
    # 그래프 저장하기
    # 존재하지 않는 정점번호를 집어넣어야함 [-1] << 그냥 넣어주는거. 0은 안됨 (정점 번호라서 )
    graph = [[-1] * 100 for _ in range(2)]
    data = list(map(int, input().split()))
    for i in range(0, E * 2, 2):
        # graph의 0번에 다른 정점 정보가 있으면 1번 넣기
        # data[i], data[i+1] : data[i]에서 data[i+1] 번으로 갈 수 있다.
        if graph[0][data[i]] == -1:
            graph[0][data[i]] = data[i + 1]
        else:
            graph[1][data[i]] = data[i + 1]

    result = dfs()
    print(f'#{tc} {result}')