[이코테] DFS/BFS

- 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 알고리즘

- 대표적인 그래프 탐색 알고리즘으로는 DFS 와 BFS가 있음

- DFS / BFS 는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야함 

 

 

스택 자료구조

- 먼저 들어온 데이터가 나가는 형식(선입후출)의 자료구조

- 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있다.

젤 먼저 넣은게 젤 나중에나감

파이썬에서는

우와...기본적으로 제공되는 객체인 리스트를 이용해서 스택 이용이 가능하대

대박...

진작에 파이썬할걸 여태 스택 구현하려고 애먹었는데,,,

 

- 최 상단원소는 제일 왼쪽에 있는걸 뽑음

- 최 하단 원소는 그대로 리스트 출력하면됨

---

큐

- 먼저 들어온데이터가 먼저나가는 선입선출의 자료구조

- 큐는 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화 할 수 있음

 

꼭 deque 라이브러리를 사용하자

 

 

왜냐면 시간복잡도를 덜 수가 있다.

append 는 리스트함수의 append 와 동일하게 동작하고

시간복잡도는 상수시간이며,

popleft는 왼쪽에 있는 메소드 - > 상수시간

파이썬에서는 이러한것이 관행이며

데이터가 오른쪽으로 들어가서 왼쪽으로 나온다고 생각하기 ( 보통 그림에서 나오는 예시와는 다르다)

역순으로 바꾸려면

reverse 를 써야한다.

특정 인덱스에 존재하는 원소 꺼내려면 원소 꺼내고 원소 위치 조정해야해서 O(k) 시간복잡도가 필요하기때문에 리스트보다 덱 라이브러리를 사용하자.

---

재귀함수

- 재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다.

- 단순한 재귀함수 예제

 재귀함수의 종료 조건

- 재귀함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야한다.

- 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.

 

팩토리얼 구현 예제

 

최대 공약수(GCD) 계산 (유클리드 호제법) 예제

- 두개의 자연수에 대한 최대 공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있다.

- 유클리드 호제법

    - 두 자연수 A,B에 대하여 ( A > B) A를 B로 나눈 나머지를 R 이라고 하자. 이때 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다.

 

- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.

- 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 많다.

---

DFS

- DFS 는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

- DFS는 스택 자료구조 ( 혹은 재귀함수) 를 이용하며, 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리한다.

방문하지 않은 인접노드가 없으면 스택에서 최상단노드를 꺼낸다.

3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

 

DFS 동작 예시

 

예상 동작 적어볼까 

-> 1-2-7-6-8-3-4-5

 

과연?

정답! ㅎㅎ

 

그럼 뭐해 코드로 짤 줄 알아야함

def dfs(graph, v, visited):
	# 현재 노드를 방문처리
    visited[v] = True
    print(v,end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
   
   재귀적 - 깊이우선으로 최대한 깊게 탐색가능
   
   #각 노드가 연결된 정보 표현(2차원 리스트)
    graph =[
    	[],
        [2,3,8],
        [1,7],
        [1,4,5]
        [3,5],
        [3,4],
        [7],
        [2,6,8],
        [1,7]
   ]
   
   # 각노드가 방문된 정보를 표현(1차원 리스트)
   visited = [False] *9
   
   #정의된 DFS 함수 호출
   dfs(graph,1,visited)
   
   인덱스 0은 사용하지 않는 방식이 더 헷갈리지 않고 직관적일 수 있다.

 

 

BFS 

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

BFS는 큐 자료구조를 이용하며, 구체적인 동작과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문처리한다.

2. 큐에서 노드를 꺼낸뒤에 해당 노드의 인접노드중에 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.

3. 더이상 2번의 과정을 수행할 수 없을때까지 반복

 

from collections import deque

#BFS 메서드 정의
def bfs(graph,start,visited):
	#큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    #현재 노드를 방문 처리
    visited[start]=True
    #큐가 빌때까지 반복
    while queue: 
    	#큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v,end=' ')
        #아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
 
 #각 노드가 연결된 정보를 표현(2차원 리스트)
 graph = [
 	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
 ]
 
 #각 노드가 방문된 정보를 표현( 1차원 리스트)
 visited = [False]*9
 
 # 정의된 BFS 함수 호출
 bfs(graph, 1, visited)

---

<문제> 음료수 얼려 먹기 : 문제 설명

연결요소 찾기 문제이다.

 

문제 풀어보자

문제 풀기

DFS or BFS 인데 둘중 머쓰지

BFS가 근처에 있는 노드 다 탐색하니까 BFS?

visited 배열마냥 매열 하나 만들고, 거기에는 1 or 0 이 들어가있음

0일때만 더 탐색하고

음..근데 한 묶음인지 어케알지...

1이 나오면 묶음 끝난걸로 알고 아스크림 개수 +1 

한담에 1주변 탐색해서 또 시작하는..

모름 그냥 해설을 보면서 익히자.

 

문제 해결 아이디어

이 문제는 DFS 혹은 BFS 로 해결가능함.

배운대로 얼음을 얼릴 수 있는 공간이 상하좌우로 연결되어있따고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있음 다음과 같이 3x3 크기의 얼음틀이 있다고 가정해보자.

 

DFS 활용 알고리즘

1. 특정 지점의 주변 상,하,좌,우를 살펴본뒤에 주변 지점중에서 값이 '0' 이면서 아직 방문하지 않은 특정한 지점이 있다면 해당 지점을 방문한다.

2. 방문한 지점에서 다시 상,하,좌,우를 살펴보면서  방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문할 수 있다.

3. 모든 노드에 대하여 1~2번의 과정을 반복하며 방문하지 않은 지점의 수를 카운트 한다. 

 

#DFS 는 계속 근접 노드 파고파고파고드는
#DFS 로 특정노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x,y):
	#주어진 범위를 벗어나는 경우에는 즉시종료
    if x<=-1 or x>=m or y<=-1 or y>=m:
    	return False
    # 현재 노드를 아직 방문 하지 않았다면
    if graph[x][y] == 0:
    	# 해당 노드 방문 처리
        graph[x][y] = 1
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False
    

#N,M을 공백을 기준으로 구분하여 입력받기
n,m = map(int,input().split())

#2차원 리스트의 맵 정보 입력받기
graph = []
for i in ragne(n):
	graph.append(list(map(int,input())))

#모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
	for j in range(m):
    	#현재 위치에서 DFS 수행
        	if dfs(i,j) ==True:
        		result +=1

print(result) #정답 출력

문제 미로 탈출 

문제 해결 아이디어

 

 

#BFS 소스코드 구현
def bfs(x,y):
	#큐 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x,y))
    #큐가 빌 때까지 반복하기
    while queue:
    	x,y = queue.popleft()
        #현재 위치에서 4가지 방향으로의 위치 확인 
        for i in range(4):
        	nx = x + dx[i]
            ny = y + dy[i]
            #미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >=n or ny <0 or ny>=m:
            	continue
            #벽인 경우 무시
            if graph[nx][ny] == 0:
            	continue
            # 해당 노드를 처음 방문하는 경우에만 최단거리 기록
            if graph[nx][ny] ==1:
            	graph[nx][ny] = graph[x][y]+1
                queue.append((nx,ny))
   	#가장 오른쪽 아래까지의 최단거리 반환
    return graph[n-1][m-1]
    
from collections import deque
    
#N,M 을 공백을 기준으로 구분하여 입력받기
n,m = map(int,input().split())
#2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
	graph.append(list(map(int,input()))

# 이동할 네가지 방향 정의 (상,하,좌,우)
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# BFS 를 수행한 결과 출력
print(bfs(0,0))

 

관련 문제풀이는 추후 같은 카테고리로 올릴예정