DFS 알고리즘 유형별 기본 틀 정리

1. 기본 스택 구현

 

방문배열 visited 초기화

 

첫 시작정점 v를 방문 처리

 

그 후 탐색 반복문 수행

 

v에 인접한 정점 w중에서 아직 방문하지 않은 w를 찾으면, 이미 방문한 v를 스택에 넣고

 

v를 w로 교체한 후에, w를 방문처리하고 바로 break

 

그 후 다시 w에 인접한 정점중에서 방문하지 않은 정점을 찾으면, w를 스택에 넣고

 

새로운 정점으로 교체한 뒤에 방문처리하고 반복 수행

 

더 이상 방문할 곳이 존재하지 않는다면 스택이 비어있는지 검사한다

 

스택이 비어있다면, 전체 탐색을 종료

 

스택이 비어있지 않다면, 하나씩 pop하여 다시 인접한 정점중에서 방문하지 않은 정점이 존재하는지 탐색 수행

 

visited = [0] * n

def dfs(v,visited):
    
    visited[v] = 1
    
    stack = []
    
    while 1:
        
        for w in adjlist[v]:
            
            if visited[w] == 0:
                
                stack.append(v)
                
                v = w
                visited[v] = 1
                
                break
        
        else:
            
            if stack == []:
                
                break
            
            else:
                
                v = stack.pop()

 

2. 기본 재귀함수 구현

 

방문배열 visited 초기화

 

시작 정점 v 방문 처리

 

v에 대한 인접한 정점 w중에서 아직 방문하지 않은 정점이라면,

 

즉시 재귀적 탐색 수행

 

visited = [0] * n

def dfs(v,visited):
    
    visited[v] = 1
    
    for w in adjlist[v]:
        
        if visited[w] == 0:
            
            dfs(w,visited)

 

3. 최적화된 스택 구현

 

이전 기본 스택 구현방식은 이미 방문했던 정점 v를 스택에 넣고, 다음 방문할 정점을 찾는데

 

그러면 더이상 방문할 정점을 찾지 못할때, 스택에서 하나씩 빼면서 뒷걸음질 치는 작업을 수행한다.

 

그런데 그래프가 너무 커버리면, 이 방법은 너무 느려서 문제

 

만약에 앞으로 방문해야할 정점 v를 모두 스택에 넣은 다음에 하나씩 빼서 탐색을 수행한다면?

 

더이상 탐색을 수행하지 못할때, 뒷걸음질 치지 않고, 즉시 다음 방문해야할 갈림길로 점프해서 빠르게 탐색을 수행

 

##########################

 

시작 정점 v를 넣은 스택으로 초기화

 

stack이 빌때까지 반복문 탐색을 수행

 

스택에서 하나의 정점을 빼고, 이미 방문한 정점이면 반복문 skip

 

방문하지 않은 정점이면 방문처리하고 인접한 정점에 대해 아직 방문하지 않은 정점을 스택에 모두 집어넣는다

 

visited = [0] * n

def dfs(v,visited):
    
    stack = [v]
    
    while stack:
        
        v = stack.pop()
        
        if visited[v] == 1:
            
            continue
        
        visited[v] = 1
        
        for w in adjlist[v]:
            
            if visited[w] == 0:
                
                stack.append(w)

 

중간에 if visited[v] == 1: continue를 반드시 수행해야하는데,

 

쓰지 않으면 for w in adjlist[v]: if visited[w] == 0: stack.append(w) 과정에서 아직 방문처리 되지 않았을때 들어간 노드가 여러번 들어가가지고,

 

어느 순간에 방문처리 되어가지고 중복해서 탐색을 수행하게 된다

 

위 코드에서는 문제 없긴한데, 문제로 노드의 방문순서를 출력해라, 어떤 노드들을 방문했는지 출력해라 등등에서 중복해서 나올 수 있다는거

 

adjlist: [[],[4,2],[4,3,1],[4,2],[3,2,1],[]],

 

stack:[1] > [4,2] > [4,4,3] >>[4,4,4] >> [4,4] > []

 

 

4. dfs를 이용한 이차원 배열 탐색

 

이차원 배열도 dfs로 당연히 탐색이 가능하다

 

델타배열 [[0,1],[1,0],[0,-1],[-1,0]]을 이용해서 4방향으로 방문이 가능한지 골라보고 가능하다면 바로 재귀경로를 생성하면서 탐색하면 된다

 

특히 미로탐색같은 경우는 때로는 그냥 미로 maze를 방문배열로 생각해서 방문배열 visited를 안만들어도 되는 경우가 많다

 

#################

 

방문배열 초기화

 

목표지점에 도달했는지 goal = False로 시작하고, global 변수로 만들어서, 목표지점에 한번이라도 도달하면 goal = True로 만들것

 

탐색을 하다가 목표지점에 도달했으면 goal= True로 바꾸고 return해서 더 이상 재귀탐색하지 않도록

 

도달하지 않았다면, 현재 좌표를 방문처리하고 [[0,1],[1,0],[0,-1],[-1,0]]로 4방향 탐색수행

 

만약 4방향 좌표가 미로 범위내에 존재하고, 미로에서 이동 불가능한 곳이 아니면서, 방문한 곳이 아니라면

 

즉시 재귀적 탐색 수행

 

이 경로 탐색을 끝내고 나서, 사용한 visited를 다시 초기화 시켜야한다.

 

visited가 고정된 값이기 때문에 현재 재귀경로 탐색하면서 visited가 탐색한 좌표는 True로 바뀌어 있는데

 

 

위와 같이 빨간색으로 탐색이 끝나고 visited를 그대로 두면, 파란색 탐색을 시작하다가 위쪽 방향도 탐색이 당연히 가능해야하는데(서로 다른 경로임) visited에서 True로 되어있어서 위로는 탐색을 못한다는게 문제임

 

그래서 dfs 끝나고 나서, 해당 좌표에 대해 visited[ni][nj] = 0으로 만드는 트릭을 반드시 기억해야함

 

visited = [[0]*N for _ in range(N)]

def dfs(i,j,N):

    global goal
    
    if maze[i][j] == 3:
        
        goal = True
        
        return
    
    else:
        
        visited[i][j] = 1
        
        for di,dj in [[0,1],[1,0],[-1,0],[0,-1]]:
            
            ni,nj = i+di,j+dj 

            if (ni >= 0 and ni <= N-1) and (nj >= 0 and nj <= N-1) and maze[ni][nj] != 1 and visited[ni][nj] == 0: 
                dfs(ni,nj,N)
                visited[ni][nj] = 0
        
        #visited[i][j] = 0 #다른 경로에서 i,j 경로를 들어온다면, 통과하도록 만들어준다..???
        
        return
    
goal = False

dfs(s,g,N)

print(goal)

 

위에서 보이듯이 for문안에서 visited[ni][nj] = 0으로 하나, 주석처리된, 전체 for문이 끝나고 visited[i][j] = 0으로 해도 결과는 동일함

 

 

5. 목표지점 경로의 수

 

목표지점에 도달할때마다 경로의 수를 1씩 증가시키기만 하면 된다

 

visited = [[0]*N for _ in range(N)]

def dfs(i,j,N):

    global answer
    
    if maze[i][j] == 3:
        
        answer += 1
        
        return
    
    else:
        
        visited[i][j] = 1
        
        for di,dj in [[0,1],[1,0],[-1,0],[0,-1]]:
            
            ni,nj = i+di,j+dj 

            if (ni >= 0 and ni <= N-1) and (nj >= 0 and nj <= N-1) and maze[ni][nj] != 1 and visited[ni][nj] == 0: 
                dfs(ni,nj,N)
                visited[ni][nj] = 0
        
        #visited[i][j] = 0 #다른 경로에서 i,j 경로를 들어온다면, 통과하도록 만들어준다..???
        
        return
    
answer = 0

dfs(s,g,N)

print(answer)

 

6. 목표지점까지의 최단 거리

 

목표지점에 도달할때마다 거리의 최솟값을 갱신하면 된다

 

특히 재귀경로를 탐색할때마다 거리를 1씩 증가시켜가며 탐색해가면 된다

 

문제에서 거리를 어떻게 정의하느냐에 따라 조금씩 달라질 수 있음

 

dfs(i,j,d,N)을 함수로 해서, 재귀경로 탐색할 때마다, dfs(ni,nj,d+1,N)으로 1씩 증가한 값을 넣으면 된다

 

최솟값 초기화도 문제 조건에 따라 주의해서 해야한다

 

visited = [[0]*N for _ in range(N)]

min_d = 10000

d = 0

def dfs(i,j,d,N):

    global min_d
    
    if maze[i][j] == 3:
        
        if min_d > d:
            
            min_d = d
        
        return
    
    else:
        
        visited[i][j] = 1
        
        for di,dj in [[0,1],[1,0],[-1,0],[0,-1]]:
            
            ni,nj = i+di,j+dj 

            if (ni >= 0 and ni <= N-1) and (nj >= 0 and nj <= N-1) and maze[ni][nj] != 1 and visited[ni][nj] == 0: 
                dfs(ni,nj,d+1,N)
                visited[ni][nj] = 0
        
        #visited[i][j] = 0 #다른 경로에서 i,j 경로를 들어온다면, 통과하도록 만들어준다..???
        
        return

 

7. 최단거리 백트래킹

 

재귀탐색은 모든 경로를 탐색하면서 최단거리를 구하기 때문에 사실 BFS가 더 효과적인데

 

탐색을 하다가 구해진 거리가, 현재 갱신된 최단거리보다 커진다면 더 탐색할 필요도 없이 재귀경로를 끊으면 된다

 

visited = [[0]*N for _ in range(N)]

min_d = 10000

d = 0

def dfs(i,j,d,N):

    global min_d
    
    #####백트래킹
    
    if min_d < d:
        
        return
    ##################
    
    if maze[i][j] == 3:
        
        if min_d > d:
            
            min_d = d
        
        return
    
    else:
        
        visited[i][j] = 1
        
        for di,dj in [[0,1],[1,0],[-1,0],[0,-1]]:
            
            ni,nj = i+di,j+dj 

            if (ni >= 0 and ni <= N-1) and (nj >= 0 and nj <= N-1) and maze[ni][nj] != 1 and visited[ni][nj] == 0: 
                dfs(ni,nj,d+1,N)
                visited[ni][nj] = 0
        
        #visited[i][j] = 0 #다른 경로에서 i,j 경로를 들어온다면, 통과하도록 만들어준다..???
        
        return