[SWEA] 1219. 길찾기 - Python

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14geLqABQCFAYD 

SW Expert Academy

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

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

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

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

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

 

다.

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

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

< ❓ 생각 >
1. 스택 사용

2. 재귀 사용

< 💻 코드 >

1.

for _ in range(1,11):
    # 테스트 케이스 번호, 길의 총 개수
    tc, num = map(int,input().split())
    # 순서쌍
    arr = list(map(int,input().split()))

    # 갈 수 있는 도시 찾기
    adj = [[-1]*100 for _ in range(2)]
    for i in range(num):
        # 첫번째 길이라면
        if adj[0][arr[i*2]] == -1:
            adj[0][arr[i*2]] = arr[i*2+1]
        # 두번째 길이라면
        else:
            adj[1][arr[i * 2]] = arr[i * 2 + 1]

    # 방문여부
    visited = [0]*100
    visited[0] = 1
    # 가는 경로
    stack = [0]
    # 기본값은 가는 길 존재 X
    result = 0
    while stack:
        top = stack[-1]
        # 도착?
        if top == 99:
            result = 1
            break
        for i in range(2):
            # 길이 있고, 방문한적 없는 곳이면 가자
            if adj[i][top] != -1 and not visited[adj[i][top]]:
                stack.append(adj[i][top])
                visited[adj[i][top]] = 1
                break
        # 길이 업다면 되돌아가기
        else:
            stack.pop()

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

2.

def graph(v):
    # 방문 표시
    visited[v] = 1
    for i in G[v]:
        # 방문한 적 없으면 방문
        if not visited[i]:
            graph(i)
    return
 
 
for _ in range(10):
    # 테스트 케이스 번호, 길의 총 개수
    tc, E = map(int, input().split())
    # 순서쌍
    arr = list(map(int, input().split()))
    
    # 방문 표시
    visited = [0] * 100
    # 갈수 있는 길 표시
    G = [[] for _ in range(100)]
    for i in range(E):
        G[arr[i*2]].append(arr[i*2+1])
        
    graph(0)
    
    print(f'#{tc} {visited[99]}')

< ❗ 느낀 점 >