ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • [알고리즘] dfs / bfs 정리
      알고리즘 2022. 9. 16. 14:59
      728x90

      DFS/BFS - 그래프 탐색 알고리즘

      트리가 깊고 해답이 깊은곳에 있다면 dfs

      트리의 뿌리 근처에 해답이 있는거 같다면 bfs

      1. 스택 자료구조 ( 선입 후출) - 입구와 출구가 같음

      • 삽입, 삭제 → append, pop → O(1)
      • 리스트 자료형 쓰기
      stack = []
stack.append(5)
stack.append(2)
stack.append(4)
stack.pop() # stack = {5,2}
print(stack[::-1]) #최상단 원소부터 출력 [2,5]
print(stack) # 최하단 원소부터 출력 [5,2]

      2. 큐 자료구조 (선입선출) - 입구 ≠ 출구

      • 삽입, 삭제 → append, popleft()
      • deque 라이브러리 사용 ( 리스트 사용 안함 )
      from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft() 

print(queue) # [2,3]
queue.reverse()
print(queue) #[3,2]

      3. 재귀함수 - 자기 자신을 다시 호출

      • 종료조건 필수
      • dfs쓸때, stack으로 사용 가능 ( stack대신에 재귀를 많이 사용함 )
      # 예시 1) 팩토리얼
# 1. 반복문
def fact(n):
	res = 1
	for i in range(1,n+1):
		res *= i
	return res

# 2. 재귀문
def fact(n):
	if n <= 1:
		return 1 # 종료조건
	return n * fact(n-1)

# 예시 2) 유클리드 호제법 -> 두 자연수에 대한 최대 공약수 구하기
# A>B -> R이 나머지:  A,B의 최대공약수 = B,R의 최대공약수 ( 반복 )
def gcd(a,b):
	if a%b == 0:
		return b
	else:
		return gcd(b, a%b)
print(gcd(192,162))

      DFS ( 깊이우선 → stack or 재귀)

      • 방문 기준에 따라 어떤 인접 노드에 접근하는지 달라짐 ( 보통은 낮은 숫자 순서)
      • 방법
        • 탐색 시작 노드를 스택에 삽입하고 방문 처리
        • 인접한 노드중 1개라도 방문하지 않은 노드가 있다면, 스택에 넣고 방문처리함
        • 인접한 노드중 1개라도 방문하지 않은 노드가 없다면, 스택에 최상위 노드를 꺼내
      graph = [
	[], # idx = 0인 부분 비워두기
	[2,3,8], # idx = 1번 노드의 주변 노드 idx 
	[1,7],  # idx = 2번 노드의 주변 노드 idx 
	[1,4,5],  # idx = 3번 노드의 주변 노드 idx 
	[3,5],
	[3,4],
	[7],
	[2,6,8],
	[1,7]
]

#각 노드가 방문된 정보 표현 ( 1차원 )
visited = [False]*9
#기본적으로 false로해서 방문하지 않음으로 초기화하기, idx=0 은 비우기위해 8이 아닌 9

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

#정의된 함수 호출
dfs(graph, 1, visited)

      BFS (너비우선 → 그래프에서 가까운 노드 우선 탐색)

      • 큐사용 ( deque )
      • 특정 노드에서 최단 경로를 구할때도 사용함
      • 간선 비용이 동일하면 bfs
      • 방법
        • 탐색 시작노드를 queue에 삽입, 방문 처리
        • 큐에서 노드를 꺼낸뒤 → 인접 노드중 방문하지 않은 노드를 모두 큐에 삽입 → 방문처리
      graph = [
	[], # idx = 0인 부분 비워두기
	[2,3,8], # 1번 노드 주변의 노드 idx 
	[1,7],  # 2번 노드 주변의 노드 idx 
	[1,4,5],  # 3번 노드 주변의 노드 idx 
	[3,5],
	[3,4],
	[7],
	[2,6,8],
	[1,7]
]

#각 노드가 방문된 정보 표현 ( 1차원 )
visited = [False]*9
#기본적으로 false로해서 방문하지 않음으로 초기화하기, idx=0은 비우기위해 8이 아닌 9

#bfs 함수 정의
from collection import deque
def bfs(graph, start, visited):
	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

#정의된 함수 호출
bfs(graph, 1, visited)

      문제1) 음료수 얼려 먹기

      수행과정

      • N*M 얼음틀, 구멍이 뚫린 부분이 0, 칸막이 있는 부분이 1 ( 세로n, 가로 m )
        • n*m이면 5개짜리 배열이 4개 [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20]]
      • 0인부분 즉, 구멍이 뚫린 부분은 상하좌우 (연결된걸로 간주) → 이 부분이 dfs or bfs 써야 함을 의미
      • 아이스크림 개수 구하기

      idea

      • 특정 노드에서 이동가능한 모든 노드를 방문처리하기
      • DFS → 특정 지점에서 주변 노드중 값이 0이면서, 방문하지 않은 지점 방문
      n,m = map(int,input().split())
graph = []
for i in range(n):
	graph.append(list(map(int,input())))

def dfs(x,y):
	# 범위 벗어나는지 체크
	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

res = 0 #카운트 하는것
for i in range(n):
	for j in range(m):
		if dfs(i,j) == True: # 현 위치에서 dfs 수행
			res += 1
print(res)
      • 모든 노드를 탐색해야하면 bfs ( que ) , 주변 노드만 탐색 bfs ( stack - 재귀 )

      문제2) 미로 탈출

      수행과정

      • N * M, (1,1)에서 1칸씩 이동해서 출구로 가기(N,M)
        • 탈출을 위해 최소한으로 이동하는 칸의 개수 세기
      • 괴물 있음 = 0, 괴물 없음 = 1
      • 칸을 카운트 할때는, 시작 과 끝 칸들도 모두 포함

      idea

      • BFS - 간선의 비용이 모두 같으며, 모든 노드를 탐색해야하므로 최단거리 구하기일때 사용함

      DFS/BFS - 그래프 탐색 알고리즘

      트리가 깊고 해답이 깊은곳에 있다면 dfs

      트리의 뿌리 근처에 해답이 있는거 같다면 bfs

      1. 스택 자료구조 ( 선입 후출) - 입구와 출구가 같음

      • 삽입, 삭제 → append, pop → O(1)
      • 리스트 자료형 쓰기
      stack = []
stack.append(5)
stack.append(2)
stack.append(4)
stack.pop() # stack = {5,2}
print(stack[::-1]) #최상단 원소부터 출력 [2,5]
print(stack) # 최하단 원소부터 출력 [5,2]

      2. 큐 자료구조 (선입선출) - 입구 ≠ 출구

      • 삽입, 삭제 → append, popleft()
      • deque 라이브러리 사용 ( 리스트 사용 안함 )
      from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft() 

print(queue) # [2,3]
queue.reverse()
print(queue) #[3,2]

      3. 재귀함수 - 자기 자신을 다시 호출

      • 종료조건 필수
      • dfs쓸때, stack으로 사용 가능 ( stack대신에 재귀를 많이 사용함 )
      # 예시 1) 팩토리얼
# 1. 반복문
def fact(n):
	res = 1
	for i in range(1,n+1):
		res *= i
	return res

# 2. 재귀문
def fact(n):
	if n <= 1:
		return 1 # 종료조건
	return n * fact(n-1)

# 예시 2) 유클리드 호제법 -> 두 자연수에 대한 최대 공약수 구하기
# A>B -> R이 나머지:  A,B의 최대공약수 = B,R의 최대공약수 ( 반복 )
def gcd(a,b):
	if a%b == 0:
		return b
	else:
		return gcd(b, a%b)
print(gcd(192,162))

      DFS ( 깊이우선 → stack or 재귀)

      • 방문 기준에 따라 어떤 인접 노드에 접근하는지 달라짐 ( 보통은 낮은 숫자 순서)
      • 방법
        • 탐색 시작 노드를 스택에 삽입하고 방문 처리
        • 인접한 노드중 1개라도 방문하지 않은 노드가 있다면, 스택에 넣고 방문처리함
        • 인접한 노드중 1개라도 방문하지 않은 노드가 없다면, 스택에 최상위 노드를 꺼내
      graph = [
	[], # idx = 0인 부분 비워두기
	[2,3,8], # idx = 1번 노드의 주변 노드 idx 
	[1,7],  # idx = 2번 노드의 주변 노드 idx 
	[1,4,5],  # idx = 3번 노드의 주변 노드 idx 
	[3,5],
	[3,4],
	[7],
	[2,6,8],
	[1,7]
]

#각 노드가 방문된 정보 표현 ( 1차원 )
visited = [False]*9
#기본적으로 false로해서 방문하지 않음으로 초기화하기, idx=0 은 비우기위해 8이 아닌 9

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

#정의된 함수 호출
dfs(graph, 1, visited)

      BFS (너비우선 → 그래프에서 가까운 노드 우선 탐색)

      • 큐사용 ( deque )
      • 특정 노드에서 최단 경로를 구할때도 사용함
      • 간선 비용이 동일하면 bfs
      • 방법
        • 탐색 시작노드를 queue에 삽입, 방문 처리
        • 큐에서 노드를 꺼낸뒤 → 인접 노드중 방문하지 않은 노드를 모두 큐에 삽입 → 방문처리
      graph = [
	[], # idx = 0인 부분 비워두기
	[2,3,8], # 1번 노드 주변의 노드 idx 
	[1,7],  # 2번 노드 주변의 노드 idx 
	[1,4,5],  # 3번 노드 주변의 노드 idx 
	[3,5],
	[3,4],
	[7],
	[2,6,8],
	[1,7]
]

#각 노드가 방문된 정보 표현 ( 1차원 )
visited = [False]*9
#기본적으로 false로해서 방문하지 않음으로 초기화하기, idx=0은 비우기위해 8이 아닌 9

#bfs 함수 정의
from collection import deque
def bfs(graph, start, visited):
	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

#정의된 함수 호출
bfs(graph, 1, visited)

      문제1) 음료수 얼려 먹기

      수행과정

      • N*M 얼음틀, 구멍이 뚫린 부분이 0, 칸막이 있는 부분이 1 ( 세로n, 가로 m )
        • n*m이면 5개짜리 배열이 4개 [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20]]
      • 0인부분 즉, 구멍이 뚫린 부분은 상하좌우 (연결된걸로 간주) → 이 부분이 dfs or bfs 써야 함을 의미
      • 아이스크림 개수 구하기

      idea

      • 특정 노드에서 이동가능한 모든 노드를 방문처리하기
      • DFS → 특정 지점에서 주변 노드중 값이 0이면서, 방문하지 않은 지점 방문
      n,m = map(int,input().split())
graph = []
for i in range(n):
	graph.append(list(map(int,input())))

def dfs(x,y):
	# 범위 벗어나는지 체크
	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

res = 0 #카운트 하는것
for i in range(n):
	for j in range(m):
		if dfs(i,j) == True: # 현 위치에서 dfs 수행
			res += 1
print(res)
      • 모든 노드를 탐색해야하면 bfs ( que ) , 주변 노드만 탐색 bfs ( stack - 재귀 )

      문제2) 미로 탈출

      수행과정

      • N * M, (1,1)에서 1칸씩 이동해서 출구로 가기(N,M)
        • 탈출을 위해 최소한으로 이동하는 칸의 개수 세기
      • 괴물 있음 = 0, 괴물 없음 = 1
      • 칸을 카운트 할때는, 시작 과 끝 칸들도 모두 포함

      idea

      • BFS - 간선의 비용이 모두 같으며, 모든 노드를 탐색해야하므로 최단거리 구하기일때 사용함

      '알고리즘' 카테고리의 다른 글

      [알고리즘] 정렬 정리  (1) 2022.09.16
      [알고리즘] 구현 정리  (0) 2022.09.16
      [알고리즘] 그리디 정리  (0) 2022.09.16
      [알고리즘] Facebook 인터뷰 - 문자열 재정렬  (0) 2022.08.20
      [알고리즘] 백준 - 18406 럭키 스트레이트  (0) 2022.08.20

      관련글 관련글 더보기

    Designed by Tistory.

    티스토리툴바