길찾기 Python(SW Expert Academy)

난이도 : D4

문제번호 : 1219

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14geLqABQCFAYD&categoryId=AV14geLqABQCFAYD&categoryType=CODE&problemTitle=%EA%B8%B8&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

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

제한

출발점은 0, 도착점은 99으로 표현된다. 정점(분기점)의 개수는 98개(출발점과 도착점 제외)를 넘어가지 않으며, 한 개의 정점에서 선택할 수 있는 길의 개수도 2개를 넘어가지 않는다. 아래 제시된 가이드 라인은 제안사항일 뿐 강제사항은 아니다.

입력

각 테스트 케이스의 첫 줄에는 테스트 케이스의 번호와 길의 총 개수가 주어지고 그 다음 줄에는 순서쌍이 주어진다. 순서쌍의 경우, 별도로 나누어 표현되는 것이 아니라 숫자의 나열이며, 나열된 순서대로 순서쌍을 이룬다.

출력

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

예시

입력	출력
홈페이지 참고	홈페이지 참고

---

2. 문제풀이

이전에 풀었던 그래프 경로와 같은 타입의 문제이다. (mungto.tistory.com/142) 여기서 데이터 편집방식만 바꿔주면 풀이가 너무 똑같아서 쓸게없다.

---

3. 소스코드

# D4 1219 길찾기
def dfs(node_index, visited, nodes):
    visited[node_index] = 1
    for node in nodes[node_index]:
        if visited[node] != 1:
            dfs(node, visited, nodes)
 
for t in range(10):
    _, E = map(int, input().split())
    nodes = [ [] for _ in range(100) ]
    input_datas = list(map(int, input().split()))
    for i in range(0, len(input_datas), 2):
        start = input_datas[i]
        end = input_datas[i+1]
        nodes[start].append(end)
    S, G = 0, 99
    visited = [ 0 for _ in range(100)]
    dfs(S, visited, nodes)
    answer = 0
    if visited[G] == 1:
        answer = 1
    print('#{} {}'.format(t+1, answer))