4871. [파이썬 S/W 문제해결 기본] 4일차 - 그래프 경로_python

문제의 저작권은 SW Expert Academy에 있습니다.

def dfs(s):
    global adj, visited, flag, goal, V  # goal:도착노드, V:정점수
    if s == goal :
        flag = 1
        return
    visited[s] = 1
 
    for i in range(1, V+1):
        if adj[s][i] == 1 and visited[i] == 0:
            dfs(i)
 
 
T = int(input())
 
for t in range(1, T+1):
    flag = 0
    V, E = map(int, input().split())  # 정점, 간선
    adj = [[0 for i in range(V+1)] for j in range(V+1)]   # 2차원 초기화
    visited = [0 for i in range(V+1)]                     # 방문처리
    for i in range(E):
        s_node, e_node = map(int, input().split()) #시작노드, 끝노드
        adj[s_node][e_node] = 1       #인접행렬
 
    start, goal = map(int, input(). split())   #출발노드, 도착노드
    dfs(start)
 
    print("#{} {}".format(t, flag))

알고리즘의 꽃은 재귀다.

그리고 dfs의 원리는 stack이다. (+ bfs는 queue라고들 한다.)

 

 

일단 dfs는 visited를 반드시 설정해 주어야 한다.

visited란 방문 한 곳을 체크하는 것을 의미하는데 보통 방문 안한 곳을 0, 방문 한 곳을 1로 체크한다.

visited를 설정해야 방문한곳을 다시 방문하지 않아서 무한루트에 빠지는 것을 막을 수 있다.

자세한것은 알고리즘 개념에서 확인하자.

 

그리고 node에 방향성이 있냐 없냐에 따라 풀이 방식이 달라진다는 점도 알아두자.