[SWEA/Python] 4871. 그래프 경로

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. dfs 적용해보기!
   dfs는 아직도 너무 어렵다😭 코드 구현은 했지만 아직도 알듯말듯,,
2. 이 문제의 경우에는 방향이 있는 경로라서 간선 입력 시 한 번만 입력하면 된다.

 

📌 코드

- 스택으로 풀기

import sys
sys.stdin = open('input.txt')

def dfs_stack(v, e):
    stack = []
    stack.append(v)

    while stack:
        v = stack.pop()

        if visited[v] == 0:
            visited[v] = 1

            for w in range(1, V+1):
                if G[v][w] == 1 and visited[w] == 0:
                    stack.append(w)
                    if w == e:
                        return 1
    return 0


T = int(input())

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

    G = [[0 for _ in range(V+1)] for _ in range(V+1)]
    visited = [0] * (V+1)

    for _ in range(E):
        x, y = map(int, input().split())
        G[x][y] = 1

    # for i in range(V+1):
    #     print('{} | {}'.format(i, G[i]))

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

    print('#{} {}'.format(t, dfs_stack(S, E)))

 

- 재귀로 풀기

import sys
sys.stdin = open('input.txt')

def dfs_reflect(v, e):
    global result
    if v == e:
        result = 1
        return

    visited[v] = 1

    for w in range(1, V+1):
        if G[v][w] == 1 and visited[w] == 0:
            dfs_reflect(w, e)

T = int(input())

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

    G = [[0 for _ in range(V+1)] for _ in range(V+1)]
    visited = [0] * (V+1)

    for _ in range(E):
        x, y = map(int, input().split())
        G[x][y] = 1

    # for i in range(V+1):
    #     print('{} | {}'.format(i, G[i]))

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

    result = 0
    dfs_reflect(S, E)

    print('#{} {}'.format(t, result))