DFS와 DFS

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

문제

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

입력

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

출력

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

 

 

bfs와 dfs탐색을 구현하는 문제, 스쿼드에서 진행한 문제이고 아직 bfs와 dfs에 대한 이해도가 모자랐기 때문에 이 문제를 풀어서 해당 개념에 대해 익숙해지려고 노력했다.

 

가장 먼저 데이터를 받아오는 코드를 작성했다.

n, m, start = map(int, input().split())

tree = {i: [] for i in range(1, n + 1)}

for _ in range(m):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

for key in tree:
    tree[key].sort()

 

먼저 가장 윗줄의 입력데이터를 순서대로 전달받는다.

n = 정점의 수

m = 간선의 수

start = 시작 노드의 번호

 

tree에 각 정점들을 key값으로 해서 딕셔너리를 생성한다. 해당 딕셔너리의 value는 모두 빈 리스트로 간선이 연결된 정점을 표시해줄 예정이다.

 

간선의 갯수만큼 반복해서 tree에 데이터를 입력한다. 이때, 해당 정점과 연결된 정점에도 동시에 추가를 해준다.

 

다음으로 딕셔너리의 각 value들을 오름차순 정렬해준다. 탐색순서를 오름차순으로 해야하기때문이다.

 

def bfs(tree, n, start, result=None):
    if result is None:
        result = []
    result.append(start)

 

dfs에 비해서 상대적으로 잘 알고있는 bfs부터 구현하기로 했다.

먼저 트리의 모양, 정점의 수, 시작점을 인자로 받고 결과를 출력할 result는 빈값으로 받았다.

(작성하면서 생각해보니 bfs는 재귀형태가 아니기 때문에 result를 인자로 받을 필요는 없었다.)

 

그리고 이미 탐색한 리스트를 표시해주기 위해서 result에 시작 정점의 값을 추가한다.

 

# def bfs(tree, n, start, result=None):
#     if result is None:
#         result = []
#     result.append(start)
    for s in result:
        if len(result) >= n:
            break
        while tree[s]:
            if tree[s][0] not in result:
                k = tree[s].pop(0)
                result.append(k)
            else:
                tree[s].pop(0)
    return result

 

반복문을 통해서 그래프를 순서대로 탐색한다. result안에 있는 모든 값들을 탐색한다.(탐색한 순서태로 result에 값이 추가되기 때문이다.)

먼저 result의 길이가 정점의 수 이상이 될 경우(모든 정점을 탐색한 경우) 반복문을 종료한다.

위의 검증을 마친 후에는 현재 정점에 연결된 모든 정점을 탐색한다. 다시 한번 조건문을 통해서 방문한적 없는 정점인 경우 result에 값을 추가하고 이미 방문한 경우 추가하지 않는다.

pop는 지나온 간선을 삭제하는 과정이다.

 

def dfs(tree, n, start, result=None):
    if result is None:
        result = []
    result.append(start)

 

이번에는 dfs를 작성한다. 해당 부분은 변수를 받고 이미 탐색한 정점을 result에 추가하는 것으로 bfs와 같은 부분이다. 단 dfs에서는 재귀함수를 사용했기때문에 result를 인자로 받는 부분이 의미가 생겼다.

 

# def dfs(tree, n, start, result=None):
#     if result is None:
#         result = []
#     result.append(start)
    while len(result) < n:
        if start not in tree or not tree[start]:
            break
        node = tree[start].pop(0)
        if node not in result:
            dfs(tree, n, node, result)
    return result

 

반복문을 통해서 result의 길이가 정점의 수보다 적은 동안만 반복을 한다. bfs와 마찬가지로 모든 정점을 탐색했기때문이다.

다음으로 탐색할 공간이 없을 경우 반복문을 종료하도록 한다. 정점의 수보다 간선의 수가 적을 경우 모든 정점을 탐색하기 전에 종료되어야하기 때문이다.

다음으로 현재 정점에서 가장 빠른 순번의 정점으로 이동한다. 다음 정점으로 이동하므로 이미 사용한 해당 간선을 삭제하고 동신에 node변수에 현재 정점의 위치를 업데이트한다.

그리고 마지막으로 node가 아직 탐색하지 않은 정점이었을 경우 재귀함수를 통해서 해당 과정을 반복한다.

 

tree_2 = copy.deepcopy(tree)

t_1 = dfs(tree, n, start)
t_2 = bfs(tree_2, n, start)

tt_1 = ' '.join(map(str, t_1))
tt_2 = ' '.join(map(str, t_2))

print(tt_1)
print(tt_2)

 

마지막으로 출력을 해준다. tree 딕셔너리를 복사한 이유는 각 과정에서 tree 딕셔너리의 값을 직접적으로 건드리기 때문이다.

이제 결과로 얻어낸 두 리스트를 출력결과에 맞도록 문자열로 바꿔준 후 출력하면 완료!

 

성공!

 

잘한건지 아닌건지 모르겠지만 아무튼 처음으로 dfs, bfs를 목적에 맞게 사용해보았다. 그리고 제한적이지만 dfs를 구현할때는 재귀함수도 사용했다. 두 개념 모두 100%이해한것은 아니지만 어느정도 사용할 수 있을 정도로는 알게되었다.

 

내일은 편안한 마음으로 코드카타를 푼 뒤에 강의를 들을 예정이다.