DFS(깊이우선탐색) / BFS(너비우선탐색)

DFS(깊이우선탐색)이란?

• 그래프 탐색 알고리즘 중 하나로 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법
• 현재 정점에서 아직 방문하지 않은 인접 정점들을 하나씩 탐색, 더 이상 탐색할 곳이 없다면 이전 상태로 되돌아가는 탐색방법
• DFS의 구현은 스택 또는 재귀 호출을 이용한다. 
• DFS는 그래프의 모든 정점을 확인하기 때문에 한정 조건이 있는 문제에서는 비효율적이다.
• 깊이 제한을 두어 조건이 만족하지 않는 경우를 무시하고 경우를 구하는 알고리즘인 백트래킹(backtracking) 사용

DFS 탐색 순서

 

DFS 구현 방법

1.  그래프의 연결 상태를 나타내는 인접 행렬(adj)과 방문한 정점인지 확인하는(visited)배열이 필요하다.

2.  방문한 정점을 True로 체크, 현재 정점과 연결되어있고 방문한적 없는 정점으로 dfs를 쭉 타고 들어간다.

3.  더 이상 타고 들어갈 정점이 없다면 이전 상태로 돌아온다.

4.  dfsAll()은 그래프의 정점들이 모두 연결되어 있지 않은 경우도 존재하기 때문에 필요하다.

 

 
def dfs(n):
    
    visited[n] = True
    
    for i in range(len(adj)):
        if adj[n][i] == 1 and visited[i] == False:
            dfs(i)
 
 
def dfsAll():
   #그래프가 연결되지 않은 경우도 있기 때문
    for i in range(len(adj)):
        if visited[i] == False:
            dfs(i)
 

 

 

dfsAll() 함수가 필요한 이유

 

---

BFS(너비우선탐색)이란?

• 깊이 우선 탐색과 함께 가장 많이 사용되는 그래프 탐색 알고리즘
• 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다.
• BFS의 구현은 큐(Queue)를 이용한다. 
• BFS는 보통 최단 경로 문제에서 많이 사용된다.

BFS 탐색 순서

 

BFS 구현 방법

1.   그래프의 연결 상태를 나타내는 인접 행렬(adj)과 방문할 정점을 체크하는(discovered)배열이 필요하다.

2.  탐색을 시작할 정점을 queue에 넣는다.

3.   현재 정점은 큐에서 꺼내고, 현재 정점과 연결되어 있으며 발견된적 없는 정점을 모두 큐에 넣는다.

4.   큐가 빌 때까지 반복한다.

 

def bfs(start):
    
    discovered[start] = True
    queue = [start]
 
    while queue:
        tmp = queue.pop()
        
        for i in range(len(adj)):
            if adj[tmp][i]== 1 and discovered[i] == False:
               queue.append(i)
                discovered[i] = True

 

---

 

DFS 와 BFS  차이 / 언제 사용하면 좋을까?

• 보통 문제들을 보면 DFS와 BFS를 둘 다 사용하여 풀 수 있다.(모든 정점들을 탐색하는 알고리즘)
• BFS는 최단경로 문제, 가중치 없는 그래프 문제에 적합하다.  > 현재 위치에서 가장 가까운 정점들을 먼저 방문하므로
• DFS는 가중치 관리가 용이하고 탐색에 대한 제약 조건이 있는 문제에 적합하다. 
• 또한 DFS는 위상정렬 문제에서도 사용 > DFS의 출력값은 위상정렬 결과의 역순과 같다.

 

 

---

추천 문제 1) 백준 2468번 안전 영역

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

2468번: 안전 영역

이 문제를 풀 때 계속 런타임에러가 났는데 찾아보니 이 문제에서 파이썬으로 DFS을 이용하여 풀 때 무조건 sys.setrecursionlimit()를 추가해야한다. 이 코드는 파이썬 재귀 깊이의 한계치를 늘려준다.  재귀 함수를 사용할 때 런타임 에러가 난다면 써주자.

 

추천 문제 2) 백준 2178번 미로 탐색

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

2178번: 미로 탐색

최소 경로 문제로 DFS를 사용하면 시간 초과 날 확률이 높다. BFS를 이용하자.

 

두 문제 모두 2차원 배열이 인접행렬을 나타내는 것이 아니라 정점 그 자체를 나타낸다. 탐색할 때 현재 위치 기준으로 상하좌우가 연결되어 있는지 모두 판단해야하기 때문에 그 부분을 추가적으로 고려해야한다.

백준 2468번 안전 영역 문제 중

 

DFS / BFS 추천 문제 n선

https://www.acmicpc.net/workbook/view/1833

문제집: DFS, BFS 추천문제 (c3171700)

 

References

알고리즘 문제해결 전략2