147p DFS예제 질문있습니다.

[TChaper]

다른방법으로 한번 풀어봤는데 순서가 약간 다르게 나옵니다.

def dfs(graph, start_node): visited, need_visit = list(), list() need_visit.append(start_node)

while need_visit:
    node = need_visit.pop()
    if node not in visited:
        visited.append(node)
        need_visit.extend(graph[node])

return visited

dfs(graph, 1)

결과값이 이렇게 출력이 됩니다. [1, 8, 7, 6, 2, 3, 5, 4]

[ndb796]

안녕하세요, @TChaper 님!

적어주신 코드는 재귀 함수를 이용하지 않고 스택을 이용한 방식으로 작성하신 것으로 보입니다.

작성하신 코드를 기반으로 정상적으로 동작하는 코드를 만들어 보았습니다.

책의 이론 파트에 적혀 있는 설명을 참고하셔서 코드를 작성해 보시며 연습하시는 것을 추천 드립니다. (137 페이지 참고)

# DFS 함수 정의
def dfs(graph, v):
    visited = [False] * (len(graph) + 1)
    # 탐색 시작 노드를 스택에 삽입하고 방문 처리
    stack = [v]
    visited[v] = True
    print(v, end=' ')
    while stack:
        # 스택의 최상단 노드
        v = stack[-1]
        for i in graph[v]:
            # 최상단 노드에 방문하지 않은 인접 노드가 있으면
            if not visited[i]:
                # 그 인접 노드를 스택에 넣고 방문 처리
                stack.append(i)
                visited[i] = True
                print(i, end=' ')
                break
        # 방문하지 않은 인접 노드가 없으면 스택에서 꺼내기
        if v == stack[-1]:
            stack.pop()

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 정의된 DFS 함수 호출
dfs(graph, 1)