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

개발/👾 PS

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

정소은 2023. 2. 5. 16:20

1. DFS, BFS에 사용되는 개념들

1) 스택과 큐

https://sosoeunii.tistory.com/21

자료구조 [ 스택 큐 덱 ]

0. < 스택, 큐, 덱 >의 기본 구조 스택, 큐, 덱은 추상 자료형(Abstract Data Type) 이다. 즉, 구현 방법이 따로 명시되어 있지 않은 것이다. (자료구조의 방법이 코드로 정의되지 않음) - 스택, 큐, 덱의 활

sosoeunii.tistory.com

2) 그래프 - 인접 리스트

그래프 = 노드 + 에지

- 노드(정점) : 데이터 표현 단위

- 에지(간선) : 노드 연결

- 가중치

인접 리스트 : 그래프의 한 노드에 연결되어 있는 다른 노드들을 하나의 연결 리스트로 표현하는 방법

3) 재귀함수

재귀함수 : 함수의 정의 과정에서 자기 자신을 다시 호출하는 함수

- 주의할 점

무한 루프에 빠지지 않도록 함수를 종료시킬 조건을 넣는다.

어디까지 계산하고 함수를 다시 호출할지 명확하게 설정한다.

함수에 input 해줄 인자(값에 영향을 주는 인자)를 명확히 한다.

재귀함수는 종료된 이후에 재귀함수가 호출된 지점 이후의 코드를 거슬러 올라가면서 수행한다 .

2. DFS, BFS 개념

탐색 알고리즘이란 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 의미한다.

DFS, BFS는 탐색 알고리즘 중에서도 완전 탐색 알고리즘에 속한다.

완전 탐색 알고리즘이란 주어진 데이터를 전부 탐색하는 알고리즘을 의미한다.

1) DFS (깊이 우선 탐색)

DFS : 그래프의 한쪽 가지를 완전히 탐색한 후 다음 가지( 가장 가까운 갈림길 )로 넘어가는 방식

* 스택 자료구조 or 재귀함수 이용

* 시간 복잡도 : O( 노드 수 + 에지 수 )

* 응용 문제 : 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등

- 구현 방법 : 재귀함수를 이용하는 방법, 스택을 이용하는 방법

( 1 ) 초기 작업

* 인접 리스트로 그래프 표현하기

* 방문 리스트 (노드 수만큼) 만들기

* 시작 노드 탐색 순서 리스트에 삽입 및 방문 체크

(2) 탐색 - 재귀함수

재귀함수 내에서 일어나는 일

- 재귀함수에 삽입한 노드 탐색 순서 리스트에 추가

- 재귀함수에 삽입한 노드 방문 체크

- 재귀함수에 삽입한 노드의 인접 노드를 하나씩 선택해 재귀함수에 삽입 ( 반복문 이용 )

* 이때 이미 방문한 노드는 제외한다.

* 이때 선택되지 못한 인접 노드는 재귀함수가 종료된 이후(가지의 끝에 도달한 이후)에 재귀함수에 삽입된다

재귀함수가 종료된 이후

재귀함수는 가지의 끝에 도달했을 때 종료된다.

종료된 이후에는 종료된 지점을 기준으로 가장 가까운 갈림길을 찾아 다시 탐색을 시작한다. - 반복문

2) BFS (너비 우선 탐색)

BFS(너비 우선 탐색) : 시작 노드를 기준으로 가까운 노드부터 탐색하는 방식

* 큐 자료구조, 반복문 사용

* 시간 복잡도 : O( 노드 수 + 에지 수 )

- 구현 방법

(1) 초기 작업

* 인접 리스트로 그래프 표현하기

* 방문 리스트 (노드 수만큼) 만들기

* 큐에 시작 노드 삽입하고 방문 체크

(2) 탐색 - 반복문을 통해 큐가 빌 때까지 반복

[1] 큐에서 노드 꺼내기 -> 꺼낸 노드를 탐색 순서에 기입

[2] 꺼낸 노드의 인접 노드를 큐에 삽입 -> 삽입한 노드의 방문 리스트 체크

* [2]단계를 수행할 때 이미 방문 리스트 체크된 노드는 큐에 삽입하지 않는다

3. DFS, BFS 기본 예제

# 1 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

# DFS 수행 과정 - 재귀함수 활용

# DFS - 스택 활용

# BFS - 큐 활용

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)
            
# DFS - 스택으로 구현

# 스택
stack = []

def dfs_stack(v):

	# 초기값 스택에 넣고 방문 체크
	stack = [v]
    visited[v] == 1
    
    # 스택이 완전히 빌 때까지 반복
	while stack:
    
    	# stack의 top pop하기
    	value = stack.pop()
        
        # 이미 방문한 노드 제외하고 탐색 순서 리스트에 추가 및 방문 체크
        if not visited[value]:
        	dfs.append(value)
            visited[value] = 1
        
        # pop한 노드의 인접 노드 스택에 넣기
        for i in node[value]:
        	if not visited[i]:
            	stack.append(i)


# BFS - 큐로 구현

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)

for i in range(N):
    if visited[i] == 0:
        DFS(i)

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

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

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

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

# 2 연결 요소의 개수 구하기 - 백준 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)
    

# DFS 함수 한번 빠져나올 때마다 cnt++
for i in range(N):
    if visited[i] == 0:
        cnt+=1
        DFS(i)   
    
print(cnt)

# 3 신기한 소수 찾기 - 백준 2023번

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

2023번: 신기한 소수

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수

www.acmicpc.net

import sys
sys.setrecursionlimit(10000) #재귀함수 깊이 제한
input = sys.stdin.readline
N = int(input())

# 소수 판별 함수
def isPrime(num):
    for i in range(2, int(num / 2 + 1)):
        if num % i == 0:
            return False
    return True

# 숫자 만들기 함수 - 소수 판별 함수에서 true가 나오면 뒤에 숫자 붙여서 다시 판별(숫자 길이가 N이 될 때까지)
def DFS(number):
    if len(str(number)) == N:
        print(number)
    else:
        for i in range(1,10):
            if i % 2 == 0:
                continue
            else:
                if isPrime(number*10+i):
                    DFS(number*10+i)

DFS(2)
DFS(3)
DFS(5)
DFS(7)

손코딩했을 때는 숫자 만드는 함수, 소수 판별하는 함수, 메인 함수(?) - 요리조리 판별해서 소수 판별 함수에 넣구 숫자 만드는 함수에 넣구

이렇게 세 개 따로따로 했는데 위 코드처럼 하는 게 덜 복잡하고 효율적인 거 같다

# 4 친구 관계 파악하기 - 백준 13023번

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

13023번: ABCDE

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

www.acmicpc.net

책에서 본 코드

import sys 
input = sys.stdin.readline 

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

# DFS - 적어도 하나의 가지의 깊이가 5이면 True
def DFS(now, depth):
    global arrive
    if depth == 5:
        arrive = True
        return
    visited[now] = True
    
    for i in A[now]:
        if not visited[i]:
            DFS(i,depth+1)
    visited[now] = False 
    
for _ in range(m):
    s, e = map(int, input().split())
    A[s].append(e)
    A[e].append(s)
    
for i in range(n):
    DFS(i,1)
    if arrive:
        break

if arrive:
    print(1)
else:
    print(0)

내가 짠 코드

import sys 
input = sys.stdin.readline 

n,m = map(int, input().split())
arrive = False
A = [[] for _ in range(n+1)]
visited = [False] * (n+1)
global cnt
cnt = 1

def DFS(now):
    global arrive
    global cnt 

    if cnt == 5:
        arrive = True
        return
    visited[now] = True
    
    for i in A[now]:
        if not visited[i]:
            cnt += 1
            DFS(i)
    cnt = 1
    visited[now] = False
    
for _ in range(m):
    s, e = map(int, input().split())
    A[s].append(e)
    A[e].append(s)
    
for i in range(n):
    DFS(i)
    cnt = 1
    if arrive:
        break

if arrive:
    print(1)
else:
    print(0)

되게 한 끗 차이 같은데 책에서 보고 쓴 코드는 맞고 내 코드는 시간초과가 난다

책에서 본 코드는 깊이 변수(depth)를 매개변수로 썼고

나는 깊이 변수(cnt)를 전역변수로 썼는데.....

이유를 모르겠다아아아아ㅠ