EC.CREW 3기 5회차 - DFS, BFS 알고리즘

개발/🌸 EC.CREW

EC.CREW 3기 5회차 - DFS, BFS 알고리즘

정소은 2023. 2. 16. 01:38

5주차 주제 : DFS, BFS 알고리즘

1. DFS, BFS 알고리즘 정리

https://sosoeunii.tistory.com/27

[ DFS, BFS ] 완전 탐색 알고리즘

1. DFS, BFS에 사용되는 개념들 1) 스택과 큐 https://sosoeunii.tistory.com/21 자료구조 [ 스택 큐 덱 ] 0. < 스택, 큐, 덱 >의 기본 구조 스택, 큐, 덱은 추상 자료형(Abstract Data Type) 이다. 즉, 구현 방법이 따로

sosoeunii.tistory.com

2. DFS, BFS 알고리즘 문제 풀이

# 1 연결 요소의 개수 - 백준 11724번

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

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주

www.acmicpc.net

import sys 
input = sys.stdin.readline 

N,M = map(int,input().split())

graph = []
visited = [0]*N
cnt=0

node = [[] for i in range(N)]

for i in range(M):
    num = list(map(int,input().split()))
    graph.append(num)
    
# 인접 요소 이차원 배열 생성
for i in range(M):
    node[graph[i][1]-1].append(graph[i][0])
    node[graph[i][0]-1].append(graph[i][1])
    
    
#DFS
def DFS(num):
    visited[num] = 1
    
    for a in node[num]:
        if visited[a-1] == 0:
            DFS(a-1)
    
    
for i in range(N):
    
    if visited[i] == 0:
        cnt+=1
        DFS(i)   
    else:
        pass
    
print(cnt)

# 2 ABCDE - 백준 13023번

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

13023번: ABCDE

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

www.acmicpc.net

# 3 DFS와 BFS - 백준 1260번

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

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

from collections import deque
import sys

input = sys.stdin.readline

N, M, V = map(int, input().split())

# 방문 리스트
visited = [0]*(N+1)

# 탐색 순서 리스트
dfs = []
bfs = []

# 인접 리스트로 그래프 표현 
node =[[]for _ in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    node[a].append(b)
    node[b].append(a)
for j in range(N+1):
    node[j].sort()

# DFS
def DFS(v):
    # 탐색 순서 리스트에 노드 삽입 
    dfs.append(v)
    
    # 삽입한 노드의 방문 리스트 체크
    visited[v]=1
    
    # 노드의 인접 노드를 재귀함수에 넣기
    for i in node[v]:
        # 이미 방문 리스트 체크된 노드는 제외
        if (visited[i]==0):
            DFS(i)

def BFS(v):
    # 큐 자료구조 생성
    queue = deque()
    
    # 탐색 순서 리스트에 시작 노드 삽입
    bfs.append(v)
    
    # 시작 노드의 방문 리스트 체크
    visited[v]=1
    
    # 큐가 빌 때까지 탐색 반복
    while(queue):
    
        # 큐에서 노드 꺼내기
        for i in node[queue.pop(0)]:
        
            # 이미 방문 리스트 체크된 노드 제외
            if(visited[i]==0):
               
               # 꺼낸 노드의 인접 노드 탐색 순서 리스트에 삽입
               bfs.append(i)
               
               # 큐에서 꺼낸 노드의 인접 노드 방문리스트 체크
                visited[i]=1
               
               # 꺼낸 노드의 인접 노드 큐에 삽입
               queue.append(i)
            
                
# 시작노드 DFS 함수에 넣기
DFS(V)

# BFS 함수 시작하기 전에 방문 리스트 초기화
for j in range(N+1):
    visited[j]=0

# 시작노드 BFS 함수에 넣기
BFS(V)

for m in dfs:
    print(m, end=' ')
print()

for n in bfs:
    print(n, end=' ')

# 4 알고리즘 수업 : 너비 우선 탐색1 - 백준 24444번

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

24444번: 알고리즘 수업 - 너비 우선 탐색 1

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방

www.acmicpc.net