문제풀이/DFS_BFS

[Python/파이썬] SW Expert Academy 1219번 길찾기

딜레이레이 2024. 6. 15. 21:57

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV14geLqABQCFAYD&categoryId=AV14geLqABQCFAYD&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=PYTHON&select-1=4&pageSize=10&pageIndex=1

 

코드

from collections import deque

for _ in range(10):
    tc, n = map(int, input().split())
    arr = list(map(int, input().split()))
    graph = [[] for _ in range(100)]
    for i in range(0, len(arr)-1, 2):
        graph[arr[i]].append(arr[i+1])

    q = deque([0])
    visited = [False]*100
    visited[0] = True
    possible = 0
    while q:
        now = q.popleft()
        if now == 99:
            possible = 1
            break
        for nx in graph[now]:
            if not visited[nx]:
                q.append(nx)
                visited[nx] = True
    print(f"#{tc} {possible}")

 

보통 경로는 한 줄에 하나씩 입력해주는데 이 문제는 특이하게 한 줄에 쭉 이어서 해준다.

그것 빼고는 별로 특이한거 없이 BFS로 풀이 가능했다.