[Python] 백준 1260 DFS와 BFS

문제 바로가기

   문제분석   

# DFS(Depth First Search) 깊이우선탐색

• 최상위 노드부터 하위 노드까지 한 길만 깊게 탐색하고 다시 위로 올라가서 다른 노드를 깊게 탐색

# BFS(Breadth First Search) 너비우선탐색

• 최상위 노드부터 다음 차수를 모두 탐색하고, 그 다음 차수를 모두 탐색하는 방법

 

 

   문제풀이   

# Depth First Search
def dfs(n):
    print(n, end=' ')
    visited[n] = True
    for i in graph[n]:
        if not visited[i]:
            dfs(i)

# Breadth First Search
def bfs(n):
    visited[n] = True
    queue = deque([n])
    while queue:
        v = queue.popleft()
        print(v, end= ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

import sys
from collections import deque

# node, branch, first node
n, m, v = map(int, sys.stdin.readline().split())
# adjacency list
graph = [[] for _ in range(n+1)]
# check list
visited = [False] * (n + 1)

# make adjacency lsit
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
# sort adjacency list
for i in range(1, n+1):
    graph[i].sort()

dfs(v)
# initialize check list
visited = [False] * (n + 1)
print()
bfs(v)

# DFS와 BFS함수를 생성한다.

• DFS는 스택과 재귀함수를 이용해 구현하고, BFS는 deque를 이용해 구현한다.

# 입력값으로 n(정점의 개수), m(간선의 개수), v(탐색을 시작할 정점의 번호)를 받는다.

# 인접 행렬을 반복문을 통해 만든다.

# 방문한 곳을 체크하기 위한 배열을 선언한다.

# 간선의 개수만큼 반복문을 돌리는데

• 간선이 연결하는 두 정점의 번호를 입력받고
• 각가 그래프 a에 b를, b에 a를 추가한다.

# 1부터 정점의 개수만큼 그래프를 sort하고 최상위 노드를 호출해 함수를 실행하도록 한다.

# 방문리스트는 false로 초기화 해놓고 함수를 통해 방문한 노드가 나올때마다 true로 바꿔준다.

 

 

 

 

몬말이지....?;;