DFS와 BFS

DFS와 BFS

코딩테스트를 준비하는 사람이라면, 누구나 반드시 공부해야하는 알고리즘 중 하나라고 한다.

나 또한 공부해야지, 공부해야지, 했지만, 이런 저런 이유를 핑계로 미뤄 두다가 이제야 다시 시작해본다.

 

DFS

깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

스택 자료구조를 이용한다.

하지만, 구현 상의 한계가 있어 스택 자료구조를 직접 이용하기 보다는 재귀 함수를 사용하여 구현한다.

def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

 

BFS

너비 우선 탐색이라고 부르며, 가까운 노드부터 탐색하는 알고리즘이다.

큐 자료구조를 이용한다.

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 not visited[i]:
                queue.append(i)
                visited[i] = True

 

자료 입력

 

n,m,start=map(int,input().split())
visited=[False]*(n+1)

graph=[[] for _ in range(n+1)]

for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(len(graph)):
    graph[i].sort()

보통 자료는 노드들의 연결 관계를 제시할 뿐이고, 1번 노드부터 순서대로 연결 관계를 보여주지는 않는다.

이에 다음과 같은 방식으로 자려 입력이 필요하다.

 

dfs와 bfs 함수에서 보면,

파라미터에 외부에서 선언된 graph와 visited를 불러오라고 명시되어있다.

하지만 굳이 파라미터에 이 둘을 넣지 않아도 동작하는 것으로 보인다.

 

 

 

 

그래도 몇 번 보니 dfs, bfs가 어떠한 모양으로 굴러가는 지는 알겠지만,

익숙해지려면 훨씬 많은 시간을 두고 적용해보아야 할 것 같다.