#131 백준 알고리즘 [1260] DFS와 BFS - 그래프

https://www.acmicpc.net/problem/1260

 

 

#Solution

http://ejklike.github.io/2018/01/05/bfs-and-dfs.html 참조하였음.

그래프 중 DFS(깊이 탐색) 그래프는 스택으로, BFS(넓이 탐색) 그래프는 큐로 구현할 수 있다.

조건이 몇가지 필요한데,

1) 연결 그래프다. 떨어진 그래프는 존재하지 않는다.

2) 정점이 여러 개 일 경우엔 작은 수부터 출력한다. 따라서 stack 이나 queue에 담을 때는 순/역순 정렬로 바꾼 뒤에 추가해준다.

3) 중복되는 수를 거르고 교집합을 쉽게 구하기 위해서 graph는 set을 사용한다.

 

인접행렬로 이 문제를 푼 사람도 있지만 나는 직관적으로 각각의 노드를 담고, 노드와 연결된 것들을 큐나 스택에 넣고, 이를 다시 소환할 때 결과 값에 넣어주는 함수를 선택했다. 알고리즘은 다음과 같다.

1) 첫 노드를 스택(큐)에 넣어준다.

2) 스택(큐)의 앞/뒤에서 pop시킨 뒤, 이를 visited 리스트에 넣어준다.

3) 방금 넣은 노드에 연결된 다른 노드 중 방문하지 않은 것들만 스택(큐)에 역순/순 정렬을 통해 넣어준다.

4) stack이 빌 때 까지 반복한다.

N, M, V = map(int, input().split())

#Graph Set
graph_list = [set([]) for _ in range(N+1)]
for _ in range(M):
    i, j = map(int, input().split())
    graph_list[i].add(j)
    graph_list[j].add(i)

#DFS
def dfs(graph_list, start):
    visited = []
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack += sorted(list(graph_list[node] - set(visited)), reverse = True)
            #스택은 뒤부터 나가니 역순 정렬
            
    return visited


#BFS
def bfs(graph_list, start):
    visited = []
    queue = [start]
    
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            queue += sorted(list(graph_list[node] - set(visited)))
            #큐는 앞부터 나가니 순정렬
    
    return visited


for i in list(dfs(graph_list, V)):
    print(i, end=" ")
print()
for j in list(bfs(graph_list, V)):
    print(j, end= " ")