[BOJ] 1260. DFS와 BFS (Python)

• 코딩 초보

---

1260. DFS와 BFS

 

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

 

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

 

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

 

---

문제를 풀기에 앞서, DFS와 BFS가 무엇인지에 대해 공부했다. 

 

DFS (깊이 우선 탐색) (Depth-First Search) 

• 그래프 탐색의 한 종류
• 최대한 깊이 내려간 뒤에 더이상 깊이 갈 곳이 없을 경우 옆 노드로 이동하여 탐색 
• 모든 노드를 방문할 필요가 있을 때 많이 사용
• 너비 우선 탐색(BFS)보다 좀 더 간단함
• 모든 노드를 방문하기 때문에 너비 우선 탐색(BFS)보다 느림 
• 보통 자기 자신을 호출하는 순환 알고리즘의 형태를 지님 
• 그래프를 탐색할 경우, 어떤 노드를 방문했었는지의 여부를 반드시 검사해야함. 
• 스택이나 재귀함수(인접행렬)로 구현 

BFS (너비 우선 탐색) (Breadth-First Search) 

• 최대한 넓게 이동한 다음, 더이상 갈 수 없을때 아래로 이동
• 깊게 탐색 전 넓게 탐색하는 것
• 두 노드 사이의 최단 경로 또는 임의의 경로를 찾고싶을때 주로 사용 
• 재귀적으로 동작하지 않음 
• 그래프 탐색의 경우 어떤 노드를 방문했었는지의 여부를 반드시 검사해야함. 
• 선입선출(FIFO) 원칙으로 탐색
• 큐를 사용하여 구현 

처음에 구현에 조금 애를 먹어서 다른 분들의 코드를 참고해서 공부했다. 

특히 DFS의 경우 재귀적으로 호출하는 로직을 이해하는데 시간이 좀 걸렸던 것 같다. 

더 많은 예제들을 풀어보면서 막힘없이 구현할 수 있도록 공부해야겠다. 

 

from collections import deque

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

a=[[]for _ in range(n+1)]
for i in range(m):
    temp=list(map(int,input().split()))
    a[temp[0]].append(temp[1])
    a[temp[1]].append(temp[0])

for i in range(n+1):
    a[i].sort()

def dfs(a,v,visited):
    visited[v]=True
    print(v,end=' ')
    for i in a[v]:
        if not visited[i]:
            dfs(a,i,visited)

def bfs(a,start,visited):
    q=deque([start])
    visited[start]=True
    while q:
        v=q.popleft()
        print(v,end=' ')
        for i in a[v]:
            if not visited[i]:
                q.append(i)
                visited[i]=True

visited=[False]*(n+1)
dfs(a,v,visited)
print()

visited=[False]*(n+1)
bfs(a,v,visited)

a는 간선정보들을 저장할 리스트. 간선의 개수 (m)만큼 temp로 입력을 받는다. 

만약 1 2 를 입력했다면, 

a의 1번째 인덱스에 있는 리스트에 2를 저장하고, 

a의 2번째 인덱스에 있는 리스트에는 1을 저장하도록 한다 (서로 연결되어 있으므로.) 

 

오름차순 순으로 탐색을 하므로 각 리스트를 sort()하여 정렬하도록 한다. 

 

dfs 함수는 재귀호출을 주로 활용한다. 그리고 방문한 노드에 대한 검사가 필요하다는 것을 염두해두자. 

시작 노드의 방문여부를 저장해놓은 visited 리스트에 해당하는 시작노드를 True로 변경하고, 해당 노드를 print 한다. 그릐고 for 반복문 안에서 더 탐색할 노드가 없을때까지 깊이 탐색하도록 dfs 함수를 재귀 호출한다. 

 

bfs 함수는 큐를 활용한다. 그리고 방문한 노드에 대한 검사가 필요하다는 것 또한 마찬가지로 염두해두자. 

큐를 활용하기 위해 collections의 deque를 import 하여 사용했다. 시작 노드 start를 먼저 큐에 넣고, visited 리스트에서 값을 True로 변경해준다. popleft를 통해 차례대로 방문한 노드를 print하도록 해준다.