[#1260] DFS와 BFS

문제

#1260 DFS와 BFS
Silver2
적용 알고리즘: DFS-BFS 알고리즘

---

풀이 방법

• DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 알고리즘을 구현한다.
• 갈 수 있는 노드가 두개 이상일 때, 오름차순으로 경로를 진행하기 위해서 각 노드의 접점을 오름차순으로 정렬한다.
• BFS의 경우 deque 라이브러리를 사용한다.

코드 흐름

1. 입력받은 값을 그래프로 구현한다.
2. 각 노드의 인접한 점들을 오름차순으로 정리한다.
3. DFS, BFS알고리즘을 수행한다.

코드

from collections import deque


def bfs(graph, v, visited):
    visited[v] = True
    print(v, end=" ")
    for i in graph[v]:
        if (visited[i] == False):
            bfs(graph, i, visited)


def dfs(graph, v, visited):
    visited[v] = True
    queue = deque([v])

    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for i in graph[node]:
            if (visited[i] == False):
                queue.append(i)
                visited[i] = True
    

n, m, v = map(int, input().split())
graph = [[] for i in range(n + 1)]

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

for i in range(n + 1):
    graph[i].sort()

visited = [False] * (n + 1)
bfs(graph, v, visited)
print()

visited = [False] * (n + 1)
dfs(graph, v, visited)

체감 난이도: 4.3/5
DFS, BFS의 알고리즘을 코드로 구성할 수 있으면 쉽게 풀 수 있는 문제였다. 진행 가능한 노드의 수가 두개 이상일 경우 적은 수부터 진행해야 하므로 알고리즘 메소드로 전달하기 전에 각각의 노드에 대한 인접 리스트를 오른차순으로 정렬해준다.