[백준] BFS와 DFS 백준 파이썬, 추천 문제, 누구나 쉽게 DFS BFS 이해시키기

BFS DFS

이제는 그만 두려워하고, BFS DFS를 완전히 정복해보자. 

 

예시문제는 백준의 BFS와 DFS이다

https://www.acmicpc.net/problem/1260

 

아이디어

1. 입력 값 받기
2. 그래프 선언
3. DFS/BFS 함수
4. 함수 실행

 

 

 

 

 

 

전체코드

from collections import deque

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

for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

# 방문 여부를 담을 리스트
visited1 = [False] * (n+1)
visited2 = [False] * (n+1)

def dfs(v):
    visited1[v] = True
    print(v, end=" ")
    
    for i in range(1, n+1):
        if not visited1[i] and graph[v][i] == 1:
            dfs(i)

def bfs(v):
    queue = deque([v])
    visited2[v] = True
    
    while queue:
        v = queue.popleft()
        print(v, end=" ")
        for i in range(1, n+1):
            if not visited2[i] and graph[v][i] == 1:
                queue.append(i)
                visited2[i] = True

dfs(v)
print()
bfs(v)

 

BFS 정리

1. queue선언 deque를 사용할 것
2. while문을 돌아 queue에 값이 없을 때 까지 반복하는 로직 구성
3. queue 맨 앞에 있는 정점을 popleft하고 갤 기준으로 방문할 수 있는 모든 정점들을 append
4. 붙인 정점들 중 가장 앞에 있는 것을 꺼내고 넣고 꺼내고 반복
5. 새로운 노드가 추가되지 않으면 그 떄까지 큐에 남아있는 것을 모두 비우고 함수를 빠져 나옴.

 

 

정리

DFS: 스택과 재귀함수로 구현할 것

BFS: deque, while로 구현

 

추천문제

• [ ] 1260 DFS와 DFS
• [ ] 2178 미로탐색
• [ ] 10451 순열 사이클
• [ ] 2331 반복 수열
• [ ] 2667 단지번호붙이기
• [ ] 2468 안전 영역
• [ ] 11724 연결 요소의 개수
• [ ] 1697 숨바꼭질
• [ ] 2606 바이러스 실3

이번주 bfs dfs 완전 내껄로 만들어 보자!