[Python, 파이썬] SWEA 1219. [S/W 문제해결 기본] 4일차 - 길찾기

A도시에서 출발하여 B도시로 가는 길이 존재하는지 알아내는 문제.

 

def DFS(i):

    global find

    if(i==99):
        find = True

    for p in graph[i]:
        DFS(p) # 자식으로 이동
        

T = 10 # 테스트케이스의 개수 T

for test_case in range(1, T+1):

    test_case, N = map(int, input().split()) # 테스트케이스 번호, 총 길의 개수
    all_ = list(map(int, input().split())) # 모든 길의 총 집합
    
    graph = [[] for _ in range(100)] # 인접 리스트

    for i in range(N):
        s, e = all_[2*i], all_[2*i+1] # 시작점, 도착점
        graph[s].append(e) # 길 저장

    # 탐색 시작
    find = False
    DFS(0)

    print("#%d %d" % (test_case, find))

 

 

 

[문제풀이]

---

 

간단한 DFS 문제.

출발점은 0, 도착점은 99다.

 

우선 모든 길을 연결리스트로 저장한다.

for i in range(N):
        s, e = all_[2*i], all_[2*i+1] # 시작점, 도착점
        graph[s].append(e) # 길 저장

 

 

그리고 이 길을 DFS를 돌려 길이 존재하는지 확인하면 끝!

for p in graph[i]:
   DFS(p) # 자식으로 이동

 

저장한 연결리스트를 가지고 출발점에서 도착점으로 점점 이동해 길의 끝에 99, 즉 도착점이 있는지 확인하기만 하면 된다.