[이코테] 탐색 알고리즘 DFS/BFS

1. DFS(Depth-First Search)

깊이 우선 탐색 : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

• 동작 원리 : 스택(Stack)
• 구현 방법 : 재귀함수
• 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘

 

1.1 구체적인 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문 처리.
3. 방문하지 않은 인접 노드가 없으면 최상단 노드 꺼내기
4. 2-3번의 과정을 더 이상 수행할 수 없을때까지 반복

'방문처리'란?

스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것!

= 1노드 1삽입

 

# graph : 탐색할 그래프, v : 시작노드, visited : 방문처리 리스트

def dfs(graph, v, visited):
	## 현재 노드 방문 처리
    visited[v] = True
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

 

 

 

 

2. BFS(Breadth First Search)

너비 우선 탐색 : 가까운 노드부터 탐색하는 알고리즘

• 동작 원리 : 큐(Queue) 
• 구현방법 : 큐(Queue) 자료구조
• 최대한 가까이 있는 노드를 먼저 탐색

 

2.1 구체적인 동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번의 과정을 더 이상 수행 할 수 없을때까지 반복하기

#from collections import deque
# graph : 탐색할 그래프, start : 시작노드, visited : 방문처리 리스트

def bfs(graph, start, visited):
	## 큐 구현 위한 deque 라이브러리 사용
    queue = deque([start])
    
	## 현재 노드 방문 처리
    visited[start] = True
    
    ## 큐가 빌 때까지 반복
    while queue:
    	## 앞에서 원소 하나 출력
    	v = queue.popleft()
        
        ## 해당 원소와 연결 안된 & 아직 방문하지 않은 원소를 큐에 삽입
        for i in graph[v]:
    		if not visited[i]:
            		queue.append(i)
                	visited[i] = True

 

 

 

 

 

3. DFS/BFS 상하좌우 관련 문제

n * m 그래프, 지도 등등 관련된 문제

 

3.1 DFS

def dfs(x, y):
	## 주어진 범위 체크 (하나라도 해당되면 False)
    if x <= -1 or x >= n 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 그래프의 문제
for i in range(n):
	for j in range(m):
    	if dfs(i, j) == 0:
    	##  ----내용변형----

 

 

3.2 BFS

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
	queue = deque()
    queue.append((x, y))
    
    
    ## 큐가 빌 때까지 반복
    while queue:
    	x, y = queue.popleft()
        
        ## 현재 위치에서 네 방향으로의 위치 확인
        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]