[백준] 1260 DFS와 BFS

백준 1260 DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다

입력

• 첫째줄: 정점의 개수 n, 간선의 개수 m, 탐색을 시작할 정점의 번호 v
• 두번재줄 ~: 간선이 연결하는 두 정점의 번호

출력

• 첫째 줄: DFS 수행 결과
• 둘째 줄: BFS 수행 결과

해결 방식

1. DFS

• 가능한 그래프에서 더 깊이 검색하는 알고리즘이다.
• 정점 v로부터 나오는 모든 간선 조사
  → v를 발견하게 해준 정점으로부터 나오는 간선을 조사하기 위해 뒤로 돌아감
• 원래 출발점으로부터 도달할 수 있는 모든 정점이 발견될 때까지 계속 반복
• 알고리즘

    depth_first_search(v):
        v 방문 표시;
        for all (v에 인접한 정점):
            is 정점이 방문 전이라면
                (v,u)를 간선을 표시;
                depth_first_search(u)
  

2. BFS: 너비 우선 탐색

• 먼저 시작 정점을 방문한 후 해당 정점과 인접한 정점을 차례대로 탐색하는 방식
• 시작 정점에 인접한 정점을 모두 방문하고, 인접한 정점과 인접해있는 정정을 방문한다.
• 가까운 거리에 있는 정점들을 차례대로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)가 필요
• 알고리즘

    BFS(v):
        v를 방문했다 표시;
        큐에 정점 V 삽입;
        while(Q가 공백이 아니라면) do
            Q에서 정점 w 삭제;
            for all (w에 인접한 정점) do
                if(u가 아직 방문되지 않았다면)
                    then u를 큐에 삽입;
                         u 방문 표시;
  

풀이

from collections import deque

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

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

def dfs(start):
    visited[start] = True
    print(start, end = " ")
    for i in graph[start]:
        if not visited[i]:
            dfs(i)

def bfs(start):
    q = deque([start])
    visited[start] = True

    while q:
        v= q.popleft()
        print(v, end=" ")
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                q.append(i)

for i in graph:
    i.sort()
visited = [False] * (n+1)
dfs(v)
print()
visited = [False] * (n+1)
bfs(v)