백준 1260번 DFS와 BFS (python 구현)

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

1260번: DFS와 BFS

DFS와 BFS 파이썬으로 구현

 

이번 1260번 문제는 낮은 정답률과는 달리 기본적인 트리 탐색방법인 DFS(Deapth-First-Search, 깊이우선탐색)과 BFS(Breadth-First-Search, 너비우선탐색)을 구현할 수 있는 가에 대한 문제였어요.

하지만 DFS나 BFS의 기본적인 개념을 모르셨던 분들께는 꽤나 어려운 문제가 되었을 것 같네요.

DFS나 BFS의 개념적인 부분 보다는 저는 어떤식으로 각각의 알고리즘을 구현할 지 좀 더 초점을 맞춰서 포스팅을 할테니, 혹시 기본 개념이 필요하신 분들은 다른 블로그를 참고하시고 난 뒤 오시는 걸 추천드릴게요 :)

먼저 DFS 깊이 우선탐색은 Recursion 재귀를 이용하여 푼 반면에, BFS 너비 우선탐색은 Queue 큐의 개념을 이용하여 풀었답니다

DFS와 BFS

이유는 DFS의 경우 검색중인 노드에서 연결된 노드가 10개가 있다면 그 중 한 노드를 먼저 탐색하고 그와 연결된 노드를 모두 탐색한 후에, 10개 중 두번째 노드를 탐색하는 형식이기 때문에 재귀를 통한 접근이 바로 떠올랐답니다. 물론 Queue를 통해서 위의 형태로 접근을 해도 무방하답니다.

반면에 BFS의 경우에는 우선 노드에 연결된 모든 노드를 탐색한 후, 다시 각각의 노드에 연결된 노드를 검색하는 level단위의 접근을 하다보니 재귀를 통하여 접근이 힘들어요!

코드에 자세한 주석을 달아놓았으니 한번 보실까요?

[V,E,start] = list(map(int, input().split())) // V: 정점 E: 간선 start:시작 노드
tree = [[] for _ in range(1001)] // 트리 건설
counter = [0 for _  in range(1001)] // 각 노드에 연결된 간선의 갯수

DFSvisited = [0 for _ in range(1001)] // 방문한 노드 알리미
DFSanswer = []

BFSvisited = [0 for _ in range(1001)] // 방문한 노드 알리미
BFSanswer = []
Q = []

for _ in range(E):
    i = list(map(int, input().split()))
    tree[i[0]].append(i[1])
    tree[i[1]].append(i[0])
    counter[i[0]] +=1 
    counter[i[1]] += 1

def DFS(TREE, n):
    if (DFSvisited[n] == 0): // 만약 아직 방문하지 않았다면
        DFSanswer.append(n) // 정답에 추가시킨 후
        DFSvisited[n] += 1 // 방문했음을 알린 후
        tree[n].sort() // 해당 노드를 작은 순으로 정렬해준 뒤
        for i in range(counter[n]): // 깊이 우선 탐색 진행
            DFS(TREE,TREE[n][i])

def BFS(TREE):
    while(len(Q)>0): // Q가 0이 될 때까지 탐색
        n = Q.pop(0) // 제일 앞에 있는 노드 호출
        BFSanswer.append(n) // 정답에 추가시킨 후
        tree[n].sort() // 해당 노드를 작은 순으로 정렬해준 뒤
        for i in range(counter[n]): // 모든 연결된 노드를 돌면서 
            if (BFSvisited[tree[n][i]]==0): // 아직 방문하지 않았다면
                Q.append(tree[n][i]) // Q에 해당 노드들을 추가시킨다.
                BFSvisited[tree[n][i]]+=1 // 방문하였음을 알린다.
        

Q.append(start) // BFS의 시작 노드 추가
BFSvisited[start]=1 // BFS의 시작 노드에 방문했음을 알린 후
BFS(tree) // 너비우선탐색 진행
DFS(tree,start) // 깊이우선탐색 진행

print(*DFSanswer) // list를 한칸씩 띄워서 프린트
print(*BFSanswer)

 

끝.