[백준 / 1260] DFS와 BFS - Python

DFS(Depth First Search)

깊이 우선 탐색

 

def dfs(graph, start_node):
    visit = []
    stack = []

    stack.append(start_node)

    while stack:
        node = stack.pop(0)
        if node not in visit:
            visit.append(node)
            stack = graph[node]+stack
    return visit

BFS(Breadth First Search)

너비 우선 탐색

 

def bfs(graph, start_node):
    visit = []
    queue = []

    queue.append(start_node)

    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])
    return visit

<부분 코드>

m,n,v = map(int, input().split())

graph = {}
for _ in range(n):
    x, y = map(int, input().split())
    
    if x in graph:
        graph[x].append(y)
    else:
        graph[x]=[y]
    if y in graph:
        graph[y].append(x)
    else:
        graph[y]=[x]

if v not in graph:
    graph[v]=[]

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

print(' '.join(map(str,dfs(graph, v))))
print(' '.join(map(str,bfs(graph, v))))

 

graph는 딕셔너리로 구현한다.

x, y의 간선은 key와 value에 모두 저장한다.

 

만약, 총노드가 1000개가 있는데 900 노드와 1000 노드가 연결된 간선이 1개밖에 없고, 1번 노드부터 탐색을 시작 시작하는 경우(입력이 1000 1 1 / 900 1000으로 주어지는 경우) v에 대한 시작 key가 graph딕셔너리에 존재하지 않으므로 v에 대한 if문에 v라는 key를 추가해준다.

 

다음 for문에서는 정점 번호가 더 작은 노드부터 방문하므로 각 value를 정렬해준다.

 

<전체코드>

def dfs(graph, start_node):
    visit = []
    stack = []

    stack.append(start_node)

    while stack:
        node = stack.pop(0)
        if node not in visit:
            visit.append(node)
            stack = graph[node]+stack
    return visit

def bfs(graph, start_node):
    visit = []
    queue = []

    queue.append(start_node)

    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node])
    return visit

m,n,v = map(int, input().split())

graph = {}
for _ in range(n):
    x, y = map(int, input().split())
    
    if x in graph:
        graph[x].append(y)
    else:
        graph[x]=[y]
    if y in graph:
        graph[y].append(x)
    else:
        graph[y]=[x]

if v not in graph:
    graph[v]=[]

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

print(' '.join(map(str,dfs(graph, v))))
print(' '.join(map(str,bfs(graph, v))))

<참고>

2021.03.19 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 깊이 우선 탐색(DFS) - Python

[보기 쉬운 Algorithm] 깊이 우선 탐색(DFS) - Python

2021.03.19 - [# Coding/# Algorithm] - [보기 쉬운 Algorithm] 너비 우선 탐색(BFS) - Python

[보기 쉬운 Algorithm] 너비 우선 탐색(BFS) - Python