# 다음과 같이 리스트 형태로 노드들의 연결 관계가 주어진다고 할 때 깊이 우선 탐색으로 이 노드들을 탐색했을 때의 순서를 공백으로 구분하여 출력하는 프로그램을 완성하세요.

# 1. **빨간색으로 Pass라고 되어 있는 부분을 완성**해주세요.

# 2. **깊이 우선 탐색을 오른쪽, 왼쪽 둘 다 구현**해보세요.

# 3. **리스트**로도 구현해보세요.

# 다음과 같이 리스트 형태로 노드들의 연결 관계가 주어진다고 할 때 깊이 우선 탐색으로 이 노드들을 탐색했을 때의 순서를 공백으로 구분하여 출력하는 프로그램을 완성하세요.

# 1. **빨간색으로 Pass라고 되어 있는 부분을 완성**해주세요.

# 2. **깊이 우선 탐색을 오른쪽, 왼쪽 둘 다 구현**해보세요.

# 3. **리스트**로도 구현해보세요.

# 1. 데이터

graph = {'E': set(['D', 'A']),
         'F': set(['D']),
         'A': set(['E', 'C', 'B']),
         'B': set(['A']),
         'C': set(['A']),
         'D': set(['E', 'F'])}

# 2. 출력
['E', 'A', 'B', 'C', 'D', 'F']

# 3. 코드

graph = {
    'A': set(['B', 'C', 'E']),
    'B': set(['A']),
    'C': set(['A']),
    'D': set(['E', 'F']),
    'E': set(['A', 'D']),
    'F': set(['D'])
}


def dfs(graph, start):
    visited = []
    stack = [start]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += graph[n] - set(visited)
    return visited


print(dfs(graph, 'E'))
