[SWEA] 4871 그래프 경로 -python

SW Expert Academy

SW Expert Academy

 

나에게 그래프가 뭔지 알려준 문제. .

이론도 쉽지 않았음 ( 하루 종일 그림 그린 사람 )

대표적인 DFS 문제다

이 코드 그냥 통으로 외워야함 !!!

def f1(start, goal, end):   # start 시작 / goal 도착 / end 마지막 정점
    visited = [0]*(end + 1)
    stack = []
    v = start   # 현재 위치
    while True:
        if v == goal:       # 현재 위치 = 목표 goal에 도달하면
            return 1        # 성공
        visited[v] = 1
        for w in range(1, end+1):
            if adjM[v][w] and visited[w] == 0:  # 인접하고 방문하지 않은 w가 있으면
                stack.append(v)                 # 현재 위치 v를 stack에 추가
                v = w
                break
            else:                               # 더이상 갈 곳이 없으면
                if stack:
                    v = stack.pop()             # stack을 pop해서 마지막 정점으로 돌아가기
                else:                           # stack이 비었으면 끝
                    break
    return 0                                    # 다돌았는데 goal에 도착하지 못했으면 실패

T = int(input())
for tc in range(1, T+1):
    V, E = map(int, input().split())
    adjM = [[0]*(V+1) for _ in range(V+1)]      # 인접행렬
    for _ in range(E):
        v,w = map(int, input().split())         # v 출발 / w 도착
        adjM[v][w] = 1                          # v에 인접한 w
                                                # 방향이 없다면 adjM[w][v] 추가하기
    start, goal = map(int, input().split())     # stack 출발 / goal 도착
    print(f'#{tc} {f1(start, goal, V)}')