문제

' 4871번 그래프 경로 '
https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AYWpDVe6hEgDFAVt&contestProbId=AYZJ9cWKdt0DFAVw&probBoxId=AYZJ8Nuadg4DFAVw&type=USER&problemBoxTitle=230214_%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&problemBoxCnt=5

Check point

📌 깊이 우선 탐색 (DFS) / Depth First Search

• 비선형 구조 ( 1 : N 관계 ) 인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색해야한다. 따라서, 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 2가지 방법으로 검색한다.
  
  
• 시작 정점의 한 방향으로 갈 수 있는 끝까지 탐색하다가 갈 곳이 없게 되면 마지막으로 만났던 갈림길 정점으로 되돌아와서 다른 방향으로 계속 탐색하여 모든 정점을 방문하는 순회방법
  
  
• 갈림길에 되돌아가서 다시 탐색을 반복하므로 후입선출 구조의 스택 사용

💡 DFS 알고리즘

1) 시작 정점 v 를 결정하여 방문
2) 정점 v 에 인접한 정점 중 방문하지 않은 정점이 있다면 v를 스택에 push하고 다음 정점 방문 / 방문하지 않은 정점이 없으면 탐색 방향 변동을 위해 스택을 pop 하여 가장 마지막 방문 정점 도출
3) 스택이 빌 때까지 2)를 반복

📌 문제 조건

• 두 개의 노드에 대해 경로가 있으면 1, 없으면 0을 출력한다.

코드

python

💡 반복문 사용

def func(start, end):
    global visit
    # 현재 위치 방문 체크
    visit[start] = True

    # 현재 위치가 목적지면 1 반환, 종료
    if start == end:
        return 1

    # 현재 위치와 연결된 모든 노드 탐색
    for vertex in graph[start]:
        # 연결된 노드의 방문 여부 확인
        if not visit[vertex]:
            # 들어갈 노드 방문 체크 해주고 재귀 호출
            visit[vertex] = True
            r = func(vertex, end)
            # 목적지에 도달해서 반환받은 1로 종료
            if r == 1:
                return 1


T = int(input())
for tc in range(1, T + 1):
    V, E = map(int, input().split())

    graph = [[] for _ in range(V + 1)]
    for i in range(E):
        s, e = map(int, input().split())
        graph[s].append(e)

    S, G = map(int, input().split())

    # 방문 체크할 배열 생성
    visit = [False] * (V + 1)

    # 목적지 도달했는지 여부로 결과 출력
    result = func(S, G)
    if result == 1:
        print(f'#{tc} 1')
    else:
        print(f'#{tc} 0')