[Algorithm] Python : DFS와 BFS

이번에 KT DS 코딩 테스트에서 정말 기본적인 BFS 알고리즘 문제를 풀지 못해 3문제 중 2솔했다 

다른분들은 다 3솔하신듯.. 항상 SQL이랑 구현 문제는 별다른 기본 지식이 필요하지 않아 걍 푸는데 다른거 나오면 손을 못댄다 ㅜ

사실 평소에 코딩 테스트 준비를 전혀 안했기도 했고, 파이썬도 코테에서 사용하기 좋다길래 2-3일 공부하고 이번에 처음 써보는거라 

역시 코테는 꾸준히 문제 풀어보고 공부해야한다고 느꼈음

 

그래서 오늘은 DFS랑 BFS 공부글을 쓴당

 

jeinalog.tistory.com/18

Python｜탐색 알고리즘 뿌시기 (1) DFS, BFS 의 개념과 구현

DFS는 Stack 사용 (스택 자료구조)

BFS는 Deque 사용 (큐 자료구조)

를 사용한다고만 알고 있었는데 이 글이 정말 왜 그 자료구조를 사용해야하는지 잘 정리한 글인듯!

 

 

 

 

 

DFS (Depth First Search)

• 깊이우선탐색 : 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
• stack을 이용해서 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아감

def dfs(graph,v,visited):
    visited[v] = True
    print(v,end = ' ')

    for i in graph[v]:
        if visited[i] != True:
            dfs(graph,i,visited)

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

visited = [False] * 9

dfs(graph,1,visited)

 

 

BFS (Breadth First Search)

• 넓이우선탐색 : 현재 정점에 연결된 가까운 점들부터 탐색
• queue를 이용하여 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣음
• queue에 넣을 시점에 해당 노드를 방문했다고 체크 (DFS는 일단 들어가서 체크)

from collections import deque

def bfs(graph,start,visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end = ' ')

        for i in graph[v]:
            if visited[i] != True:
                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]
]

visited = [False] * 9

bfs(graph,1,visited)