[알고리즘]- 탐색(DFS,BFS) + 문제

1. DFS(깊이 우선 탐색) - 스택/재귀 함수

시작 정점에서부터 임의의 방향으로 갈수있는 곳까지 깊이 탐색하다가 더이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길로 되돌아와 다른 방향을 다시 탐색합니다.

탐색은 아직 방문하지 않은 정점에 대해서만 진행해야하므로 방문한 정점에는 반드시 표시를 해둬야합니다.

 

먼저, 재귀로 작성한 코드입니다.

def dfs(graph, v, visited): 
    visited[v] = True # 방문 처리
    print(v, end=' ') 
    for i in graph[v]: # v번 노드와 연결된 노드들
        if not visited[i]: # 방문하지 않았으면
            dfs(graph, i, visited) # 방문하기

graph = [ # n번 노드와 연결된 정보들
    [],
    [2,3,8], 
    [1,7], 
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * len(graph) # 방문 안함을 False로 표시

dfs(graph, 1, visited)

두번째로는 스택을 이용하여 작성한 코드입니다.

def dfs_stack(graph, start):
    visited = [False] * len(graph)  # 방문 여부를 저장
    stack = [start]  # 시작 노드를 스택에 추가

    while stack:  # 스택이 빌 때까지 반복
        v = stack.pop()  # 스택에서 가장 위의 노드를 꺼냄

        if not visited[v]:  # 방문하지 않았다면
            print(v, end=' ')  # 현재 노드 출력
            visited[v] = True  # 방문 처리

            # 현재 노드와 연결된 노드를 스택에 추가
            # (역순으로 추가해야 DFS 순서가 올바르게 유지됨.)
            for i in sorted(graph[v], reverse=True):
                if not visited[i]:
                    stack.append(i)

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

dfs_stack(graph, 1)

 

2. BFS(너비 우선 탐색) - 큐

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문합니다. 최단 경로를 구할때 많이 사용됩니다.

deque를 사용하지 않고 리스트로 구현을하면 dfs와 스택과 큐말고는 차이가 없습니다.

def bfs(graph, start):
    visited = [False] * len(graph)  # 방문 여부를 저장
    queue = [start]  # 큐를 리스트로 생성
    visited[start] = True  # 시작 노드 방문 처리

    while queue:  # 큐가 빌 때까지 반복
        v = queue.pop(0)  # 큐의 첫 번째 요소를 꺼냄
        print(v, end=' ')  # 현재 노드 출력

        # 현재 노드와 연결된 노드들을 큐에 추가
        for i in graph[v]:
            if not visited[i]:  # 방문하지 않은 노드라면
                queue.append(i)  # 큐에 추가
                visited[i] = True  # 방문 처리

graph = [
    [],
    [2, 3, 8],  
    [1, 7],     
    [1, 4, 5],  
    [3, 5],     
    [3, 4],     
    [7],        
    [2, 6, 8],  
    [1, 7]     
]

bfs(graph, 1)

 

deque를 사용하면 시간효율이 좋습니다. 

from collections import deque

def bfs(graph, start):
    visited = [False] * len(graph)  # 방문 여부를 저장
    queue = deque([start])  # 시작 노드를 큐에 추가
    visited[start] = True  # 시작 노드 방문 처리

    while queue:  # 큐가 빌 때까지 반복
        v = queue.popleft()  # 큐에서 가장 앞의 노드를 꺼냄
        print(v, end=' ')  # 현재 노드 출력

        # 현재 노드와 연결된 노드들을 큐에 추가
        for i in graph[v]:
            if not visited[i]:  # 방문하지 않은 노드라면
                queue.append(i)  # 큐에 추가
                visited[i] = True  # 방문 처리

graph = [
    [],
    [2, 3, 8],  
    [1, 7],     
    [1, 4, 5],  
    [3, 5],     
    [3, 4],     
    [7],       
    [2, 6, 8],  
    [1, 7]     
]

bfs(graph, 1)

 

 

아래는 프로그래머스에서 dfs를 이용하여 푼 문제입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

visited=[] # 방문 여부 저장
def dfs(k,dungeons,cnt):
    max_cnt=cnt # 최대 던전 수
    for i in range(len(dungeons)):
        if i not in visited and dungeons[i][0]<=k: # 방문하지 않고 최소 피로도가 k 이하일때
            visited.append(i) # i번째 방문
            max_cnt=max(max_cnt,dfs(k-dungeons[i][1],dungeons,cnt+1)) # 모든 노드들 방문
            visited.pop() # 방문 비워주기
    return max_cnt

def solution(k, dungeons):
    cnt=dfs(k,dungeons,0)
    return cnt