[BOJ] 1260 - DFS와 BFS

[BOJ] 1260 - DFS와 BFS

문제

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력

1 2 4 3
1 2 3 4

문제 해결

기본적인 DFS, BFS 문제이다. 이미 다른 곳에서 이와 관련된 내용은 많이 다루고 있으니 다루지는 않고 구현 과정에 집중해 설명하겠다.
순서는 다음과 같다

1. graph 라는 딕셔너리에 간선들을 토대로 연결된 노드들을 표시한다. 노드들은 집합 자료형을 이용하였다.
ex) 
{
    1 : {2, 3, 4},
    2 : {1, 4},
    3 : {1, 4},
    4 : {1, 2, 3}
}
2. dfs 탐색을 한다.
2-1. 방문했던 노드를 기억하는 배열 visited 와 현재 노드들이 쌓여있는 스택 temp 를 만든다.
2-2. 스택이 빌떄까지 순회하면서 방문하지 않은 노드의 자식 노드들을 스택에 쌓는다.
2-3. 단 자식노드들을 쌓을 때 현재 방문했던 노드와 차집합하여 또 방문하는 일이 없도록 한다.
2-4. 그리고 set 자료형은 순서를 보장하지 않기 때문에 정렬을 해주면서 쌓는다.
2-5. 작은 노드부터 탐색하기 위해 sorted 에 reverse 옵션을 사용한다.
3. bfs 탐색을 한다.
3-1. dfs와 비슷하나 앞에 요소를 꺼낸다는 점(queue), 정렬할 때 reverse 옵션을 사용하지 않는 다는것만 신경써서 알고리즘을 구상한다.
4. 주의할 점은 시작요소와 연결된 간선이 없을 때 조건을 걸어주어야 한다는 것

python 코드

graph = {}

def setGraph (m) :
    for _ in range(0, m):
        nodeA, nodeB = map(int, input().split())
        if not nodeA in graph :
            graph[nodeA] = set([])
        if not nodeB in graph : 
            graph[nodeB] = set([])

        graph[nodeA].add(nodeB)
        graph[nodeB].add(nodeA)

def bfs(start):
    if not start in graph :
        print(start)
        return
    visited = []
    temp = [start]
    while temp :
        n = temp.pop(0)
        if not n in visited :
            visited.append(n)
            temp.extend(sorted(list(graph[n] - set(visited))))
    visited = list(map(str, visited))    
    print(" ".join(visited))

def dfs(start):
    if not start in graph :
        print(start)
        return
    visited = []
    temp = [start]
    while temp :
        n = temp.pop()
        if not n in visited :
            visited.append(n)
            temp.extend(sorted(list(graph[n] - set(visited)), reverse=True))
    visited = list(map(str, visited))
    print(" ".join(visited))

def main () :
    n, m, v = map(int, input().split())
    setGraph(m)
    dfs(v)
    bfs(v)

main()

느낀 점

알고리즘을 풀면서 기록을 남기는 것도 좋겠다고 생각해서 포스팅을 해보고 있다. 오래걸린 문제나 오랜 고민을 하게된 문제가 있으면 종종 포스팅하겠다.