<aside> 🔥 DFS와 BFS 문제 링크

</aside>

문제 정리

<aside> 🔥 입력값 1 - 정점의 개수 n

입력값 2 - 간선의 개수 m

입력값 3 - 탐색을 시작할 정점의 번호 v

입력값 4 - n+1개의 줄에 두 정점이 연결된 간선이 입력된다.

출력값 1 - v부터 시작해 dfs로 탐색한 결과 출력

출력값 2 - v부터 시작해 bfs로 탐색한 결과 출력

</aside>

예제로 정리

# 입력값
4 5 1
1 2
1 3
1 4
2 4
3 4

# 출력값
1 2 4 3
1 2 3 4

접근 방법

<aside> 🔥 (1) 노드와 노드의 연결 입력값을 토대로 양방향 1차원 그래프를 만든다.

(2) v부터 시작해서 탐색.

</aside>

코드 진행

<aside> 🔥 입력값을 받아 그래프를 만들어준다.

그리고 그래프의 요소들을 오름차순으로 정렬해준다. (안해줄 경우 순서대로 방문하지 않는다.)

</aside>

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

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 graph:
    i.sort()

<aside> 🔥 dfs 탐색은 재귀함수로 작성해보았다.

visited 리스트에 방문한 지점을 순차적으로 넣어줬다.

</aside>

def recursive_dfs(graph, start, visited):
    visited.append(start)
    for adj in graph[start]:
        if not adj in visited:
            recursive_dfs(graph, adj, visited)
    return " ".join(map(str, visited))

<aside> 🔥 bfs 탐색은 queue를 이용했다.

</aside>

def bfs(graph, start, visited):
    visited.append(start)
    queue = collections.deque([start])
    while queue:
        front = queue.popleft()
        for adj in graph[front]:
            if not adj in visited:
                visited.append(adj)
                queue.append(adj)
    return " ".join(map(str, visited))