[김태원 알고리즘] 경로탐색 (그래프 DFS)

사용 언어: Python3

문제

풀이

내 풀이

def DFS(cur, S): # current node, start node
    if cur == N:
        path.append(cur)
        print(' '.join(map(str,path)))
        path.clear()
        path.append(1)
    else:
        for i in range(S, N+1):
            if G[cur][i] == 1 and visited[i] == 0:
                path.append(cur) # 지나가기
                visited[i] = 1
                DFS(i, S+1)
                visited[i] = 0

N, M = map(int, input().split())
G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    s, e = map(int, input().split())
    G[s][e] = 1

visited = [0] * (N+1)
path = [1]
DFS(1, 1)

• 실패

다른 풀이

def DFS(v): # v = current node
    global cnt
    if v == N:
        cnt += 1
        print(' '.join(map(str, path)))
    else:
        for i in range(1, N+1):
            if G[v][i] == 1 and visited[i] == 0:
                visited[i] = 1
                path.append(i)

                DFS(i)

                visited[i] = 0
                path.pop()


N, M = map(int, input().split())
G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    s, e = map(int, input().split())
    G[s][e] = 1

visited = [0] * (N+1)
visited[1] = 1 # 1번 노드는 무조건 방문
path = [1] # 경로

cnt = 0
DFS(1)

print(cnt)

내 풀이 - 0527 추가

import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
visited = [0] * (N+1)

# init Graph
for _ in range(M):
    s, e = map(int, input().split())
    G[s].append(e)

def DFS(v, path):
    visited[v] = 1
    if v == N:
        res.append(path)
        return
    for x in G[v]:
        if not visited[x]:
            visited[x] = 1
            DFS(x, path + [x])
            visited[x] = 0 # ✅ 다시 돌려놓기

res = [] # 경로들 저장
DFS(1, [1]) # ✅ path까지 전달

for row in res:
    print(row)
print(len(res))

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기