TIL 004 DFS / BFS

조성현·2020년 12월 27일

TIL 알고리즘

정글

목록 보기

5/21

📕 DFS(Depth First Search) / BFS(Breadth First Search)

👉 사용목적

DFS: 다차원 배열에서 각 칸을 방문할때 깊이를 우선으로 방문, 현재 정점에서 갈 수 있는 곳까지 가보며 탐색.

BFS: 다차원 배열에서 각 칸을 방문할때 너비를 우선으로 방문, 현재 정점에서 연결된 주변의 가까운 노드부터 탐색.

출처: https://namu.wiki/w/BFS

👉 구현방법

기본적인 형식은 다음과 같다. visited array를 사용해 방문한 곳은 다시 방문하지 않도록 해야한다.

#R = number of row 
#C = number of column

# 주어진 array
A=[[0 for _ in range(C)] for _ in range(R)] 

# 방문한 곳을 표기하기 위한 array
vis=[[0 for _ in range(C)] for _ in range(R)] 

# 탐색 커서 (상하좌우)
dr = [1,0,-1,0]
dc = [0,-1,0,1]

DFS: 스택, 재귀로 구현

# 스택
while(stack):
    cur = stack.pop()
    for j in range(4)
       c = cur + j
       if vis[c] == 1: continue
       if 범위 밖 or 갈 수 없는 곳 : continue
       stack.append(c)
       vis[c] = 1

# 재귀
def dfs(i):
    vis[i] = 1;
    for j in range(4)
       c = i + j
       if vis[c] == 1: continue
       if 범위 밖 or 갈 수 없는 곳 : continue
       dfs(c);

BFS: 큐로 구현

# 큐
while(queue):
    cur = queue.popleft()
    for j in range(4)
       c = cur + j
       if vis[c] == 1: continue
       if 범위 밖 or 갈 수 없는 곳 : continue
       queue.append(c)
       vis[c] = 1

👉 유형

한 노드와 연결되 있는 모든 노드 탐색하는 유형이 전형적이다. 이때는 DFS, BFS 아무거나 써도 되지만, 특별한 유형들도 있다.

DFS

경로 찾기 -> 여러 경로를 고려해야 할때, 재귀 사용

def dfs(i):
    for j in range(4)
       c = i + j
       if vis[c] == 1: continue
       if 범위 밖 or 갈 수 없는 곳 : continue
       vis[c] = 1
       dfs(c);
       vis[c] = 0

사이클 찾기 -> 시작점을 따로 저장해둔다.

def dfs(i):
    vis[i] = 1;
    for j in range(4)
       c = i + j
       if vis[c] == 1 (시작점인지 확인):
           return "cycle"
       dfs(c);

위상정렬 -> 차수를 저장하고, 진입 차수가 0인 node 부터 넣는다.

 for i in range(N):
     if order[i] == 0:
         stack.append(i)
         ans.append(i)
 while(stack):
     cur = stack.pop()
     order[cur] = -1 # 방문했다는 표시
     for i in range(len(A[cur])):
         order[A[cur][i][0]] -= 1
         if order[i] == 0:
            stack.append(A[cur])

BFS

최단거리 -> BFS를 쓰면 주변을 먼저 탐색하기 때문에, 먼저 탐색되는 거리가 자동으로 최단거리다.

# 큐
while(queue):
    cur = queue.popleft()
    거리 = cur[1]
    for j in range(4)
       c = cur + j
       if vis[c] == 1: continue
       if 범위 밖 or 갈 수 없는 곳 : continue
       stack.append([c, 거리+1])
       vis[c] = 1

여러 개의 최단거리 -> while 문을 추가해 큐가 빌 때까지 탐색

    while(1):
        cursize = len(queue)
        while(cursize):
            cur = queue.popleft()
            for i in range(len(A)):
                newcur = cur + A[i]
                if newcur > K: continue
                if vis[newcur]==True: continue
                queue.append(newcur)
                vis[newcur]=True
            cursize-=1
        cnt += 1