[Python] 백준 1260 : DFS와 BFS

문제:

 

 

코드 : 

import sys
from collections import deque

# 방문 : 1 & 방문x : 0

def DFS(V):
    visited_dfs[V] = 1
    print(V, end= ' ')

    for i in range(1, N+1):
        if visited_dfs[i] == 0 and graph[V][i]==1:
            DFS(i)
    

def BFS(V):
    queue = deque([V])
    visited_bfs[V] = 1

    while queue:
        V = queue.popleft()
        print(V, end= ' ')

        for i in range(1, N+1):
            if visited_bfs[i] == 0 and graph[V][i] == 1:
                queue.append(i)
                visited_bfs[i] = 1


    
input = sys.stdin.readline

# 정점의 개수, 간선의 개수,탐색 시작 정점 번호
N, M, V = map(int, input().rstrip().split())

# 방문 정점 리스트
visited_dfs = [0]*(N+1)
visited_bfs = [0]*(N+1)

# 그래프
graph = [[0]*(N+1) for _ in range(N+1)]

# 간선 입력 & 연결
for i in range(M):
    n1, n2 = map(int, input().rstrip().split())
    graph[n1][n2] = graph[n2][n1] = 1

DFS(V)
print()
BFS(V)

 

 

풀이:

DFS

- 깊이 우선 탐색 / 스택 or 재귀로 구현 가능 / 보통 재귀로 구현

- 경로의 특징 저장 가능해서 관련 문제에 사용!

- graph[][] 생성 후 간선 입력 받아서 1로 지정 해주기 / 방문 정점 리스트 생성

 

BFS

- 너비 우선 탐색 / 큐로 구현

- 최단거리 문제에 사용!

- deque 공부 좀 더..