SWE(4871)_그래프 경로

작성일 | In

SWE 4871 그래프 경로

문제이해

V개 이내의 노드를 E개의 간선으로 연결한 방향성 그래프에 대한 정보가 주어질 때, 특정한 두 개의 노드에 경로가 존재하는지 확인하는 프로그램을 만드시오

두 개의 노드에 경로가 있으면 1, 없으면 0을 추력한다

노드 번호는 1번부터 존재하며, V개의 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.

그 전에 나동빈님 실전알고리즘 강의 수강

BFS(너비 우선 탐색) 시작점과 가까운 것 위주로 먼저 탐색. 맹목적인 탐색을 하고자 할 때, 사용하는 탐색 기법 최단경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 사용한다. 준비물은 큐

1번이라고 하면. 1번 시작하므로 우선 방문 -> 색을 빨간색으로 그 이후 이 알고리즘 반복

  1. 큐에서 하나의 노드를 꺼낸다
  2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고 차례대로 큐에 삽입한다.

[BFS나동빈님 블로그]https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230944971&referrerCode=0&searchKeyword=BFS

vector 클래스에 push_back 함수를 지원해주는 것 같다.

DFS(깊이 우선 탐색) 맹목적으로 각 노드 탐색시 사용. stack이 사용. 실제로 stack을 사용하지 않아도 재귀함수 이용하면 구현할 수 있긴 하다. 같은 효과. 함수 호출이 스택으로 구현한거니까.

BFS 알고리즘.

  1. 스택의 최상단 노드를 확인한다
  2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 뺸다.

해리님 코드 분석

알게된 것

  1. 이차원 리스트로 간선에 대한 입력을 받으며, 주로 0은 인덱스로 사용하지 않고 1부터 사용한다 (노드번호가 1부터니까)
  2. print() 함수에 f 문자열을 쓸 수 있는데, 포맷 문자열로, 문자열에 f를 붙이고 표현식을 작성하여 문자열에 파이썬 표현식의 값을 삽입할 수 있게 한다.
    • ex : print(f'The value of pi is approximately {math.pi:.3f} (import math 한 뒤 )
    • 출력값 : The value of pi is approximately 3.142
Map = []
visited = []
start_node = 0
end_node = 0


def DFS(start):
    global result
    visited[start] = 1  # 시작노드는 방문한 노드니까 1 넣는다
    for next in range(1, v+1):  # 1이 갈 수 있는 경로를 리스트 돌며 탐색
        # 간선이 있으면서 (값이 1이면서) 방문하지 않은 노드라면
        if Map[start][next] and not visited[next]:
            if next == end_node:  # end node와 같다면
                result = 1   # 경로가 있음을 표시해주고 나간다
                return
            DFS(next)  # 재귀함수적으로 다음 깊이로 들어간다.
            # 예를 들어 3일 때, 1이지만 visited 없다. 그러면 3을 넣고 함수 반복
            # 3은 방문했으니 visited에서 1로 변경하고 갈 수 있는 경로 탐색 없으니 함수 다시 빠져나오고
            # 4 방문, visited에 없으니 4를 넣고 DFS 함수 시작 4가 갈 수 있는 경로 탐색 -> 6이 있네
            # 6 방문, visited에 표시. 6이 endNode이므로 -> 종료


if __name__ == "__main__":
    TC = int(input())
    for tc in range(1, TC+1):
        v, e = map(int, input().split())
        # map을 이차원 리스트로 만들어주는데, 노드가 1부터 존재하므로, 인덱스를 1부터 사용하기 위해 v+1을 곱해줌
        Map = [[0]*(v+1) for _ in range(v + 1)]  # 그래프를 표시할 Map
        visited = [0]*(v+1)  # 방문을 표시할 리스트
        for i in range(e):  # 간선 수만큼 반복
            start, end = map(int, input().split())  # 간선 입력 받기
            Map[start][end] = 1

        # 경로의 존재를 확인할 출발 노드 S와 착노드 G
        # 1에서 6으로 가는 경로를 찾아라
        start_node, end_node = map(int, input().split())
        result = 0
        DFS(start_node)
        print(f'#{tc} {result}')

참고자료 [참고답안]https://tothefullest08.github.io/algorithm/2019/03/07/3_4871_%EA%B7%B8%EB%9E%98%ED%94%84%EA%B2%BD%EB%A1%9C/ [BFS]https://www.youtube.com/watch?v=66ZKz-FktXo&t=354s [포맷 문자열 리터럴]https://docs.python.org/ko/3/tutorial/inputoutput.html

0%