DFS/BFS

yejichoi·2023년 4월 26일
0

알고리즘 스터디

목록 보기
48/153
post-thumbnail

탐색

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 i.e) DFS/BFS

스택

First In Last Out
Last In First Out

스택 예제

stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # [5, 2 ,3,1]
print(stack[::-1]) #[1, 3, 2, 5]

append(), pop()

append() 메소드는 리스트의 가장 뒤쪽에 데이터 삽입
pop() 메소드는 리스트의 가장 뒤쪽에 데이터 제거

큐

First In First Out

from collections import deque
# 큐 구현을 위해 deque 라이브러리 사용
queue = deque()


queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) #먼저 들어온 순서대로 출력, [3,7,1,4]
queue.reverse()
print(queue) # 나중에 들어온 순서대로 출력 [4,1,7,3]

재귀함수

내부적으로 스택 자료구조와 동일 i.e) DFS

# 반복적으로 구현한 n!
def factorial_iterative(n):
	result = 1
    
    for i in range(1, n+1):
    	result *= i
    return result 
    
#재귀적으로 구현한 n!
def factorial_recursive(n):
	if n <=1:
    	return 1
    return n * factorial_recursive(n-1)
    # n * (n-1) * ... 1

DFS

  • ⭐️ 스택 자료구조 이용

  • Depth-First Search(깊이우선탐색)

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

  • DFS의 기능을 생각하면 순서와 상관없이 처리해도 되지만, 코딩 테스트에서는 번호가 낮은 순서부터 처리하도록 명시하는 경우가 있음 -> 번호가 낮은 순서부터 구현하기

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

    인접 행렬

    연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 잓ㅇ

    INF = 99999999999 #

graph = [
  [0,7,5],
  [7,0,INF],
  [5,INF,0]
]

    인접 리스트

    특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적음 

    #행(row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [ [] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))
 
graph[1].append((0,7))
 
graph[2].append((0,5))

print(graph)
#[[(1,7), (2,5)], [(0,7)], [(0,5)]]

    DFS 예제 -재귀함수 및 스택 이용

    #DFS 메소드 정의
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 -> graph[1] = [2,3,8], 제일 작은 노드 2 방문 -> 
 #graph[2] = [1,7], 1은 방문 했으니 노드 7 방문 -> ...
 
 
 # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
 visited = [False] * 9 # 기본값 false , 인덱스 0 을 사용하지 않기 위해 노드 + 1  
 
 #함수 호출 
 dfs(graph, 1, visited) # 1 2 7 6 8 3 4 5

    BFS

  • ⭐️ 큐 사용

  • DFS 보다 구현이 조금 더 빠름

  • Breadth First Search(너비 우선 탐색)

  • 가까운 노드부터 탐색하는 알고리즘

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

    BFS 예제

    from collections import deque

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 제거-> graph[1] = [2,3,8], 모두 방문 (근접 기준) -> 
#graph[2] = [1,7], 1은 방문 했으니 노드 7 방문 -> 
#graph[3] = [1,4,5], 1은 방문했으니 4,5 방문 -> ... 
 
 
 
  # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
 visited = [False] * 9 # 기본값 false , 인덱스 0 을 사용하지 않기 위해 노드 + 1  
 
 #함수 호출 
 bfs(graph, 1, visited) # 1 2 3 8 7 4 5 6

    스택 메소드 : append(), pop()

    큐 메소드 : appendleft(), pop(), append(), popleft()

    왼쪽에 값을 입력할 때 appendleft()
    오른쪽에 값을 입력할 때 append()
    왼쪽에서 값을 빼고 싶다면 popleft()

    음료수 얼려 먹기

    DFS로 하나의 깊이 우선 탐색이 끝나면 카운트 

    n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기 
graph = []
for i in range(n):
	graph.append(list(map(int, input().split())))
#dfs로 특정한 노드를 방문한 뒤에 연결된 모든 노드 방문
def dfs(x,y):
	# 주어진 범위 벗어나면 종료 
	if x >=n or x <= -1 or y >=m or y <= -1:
   	return False
       
    #현재 노드를 아직 방문하지 않았다면
   if graph[x][y] == 0:
   		graph[x][y] = 1 # 방문처리
   		#상,하,좌,우 재귀함수
           dfs(x-1,y)
           dfs(x+1,y)
           dfs(x,y-1)
           dfs(x,y+1)
           return True
      return False
      
      #모든 노드에 대해서 음료수 채우기
      result = 0
      for i in range(n):
      	for j in range(m):
       	if dfs(i,j) == True:
           	result += 1
print(result)               
# N, M을 공백으로 구분하여 입력 받기
n, m = map(int, input().split())

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

# 상하좌우 진행용 방향 리스트
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 아이스크림 개수
count = 0

# dfs를 통해 현재 노드를 방문한 뒤, 연결된 모든 노드들을 방문
def dfs(start_x, start_y):

    # 현재 노드를 방문 처리
    ice_board[start_x][start_y] = 1

    # 현재 노드와 인접한 모든 노드들을 탐색하며, 방문 가능할 경우 방문
    for i in range(4):

        # 인접 노드 좌표
        nx = start_x + dx[i]
        ny = start_y + dy[i]

        # 인접 노드가 얼음판 내부에 위치할 경우
        if (nx >= 0 and nx < n and ny >= 0 and ny < m):

            # 인접 노드에 음료수를 채울 수 있는지 확인
            if (ice_board[nx][ny] == 0):

                # 인접 노드 방문
                dfs(nx, ny)

# 모든 위치에 음료수 채우기
for i in range(n):
    for j in range(m):
        # 해당 노드에 음료수를 채울 수 있다면
        if (ice_board[i][j] == 0):
            # 해당 노드에서 dfs 탐색 시작
            dfs(i,j)
            count += 1

print(count)
profile
yejichoi
Hi
이전 포스트

구현

다음 포스트

(DFS/BFS) 타겟 넘버

0개의 댓글