CS/알고리즘

[알고리즘] DFS/BFS

삶_ 2022. 6. 26. 15:18

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

  • 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

DFS

  • 깊이를 우선으로 하는 탐색
  • 스택자료구조(혹은 재귀함수)를 이용.
    1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다
    2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문처리함.
    3. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다
    4. 더이상 2~3 과정을 수행할 수 없을때까지 반복
#다 골고루 방문해서 (중복없이) 출력하는것. 위 그림을 보고 아래를 만듬.

#숫자 오름차순대로 방문한다고 생각하고 짜기
#각 노드가 연결된 정보 표현. 0번째는 비워두기!
graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]

#각 노드가 방문된 정보 표현
visited = [False] * len(graph)

#정의된 dfs함수 호출
dfs(graph, 1, visited) #1에서 시작

#dfs함수 정의
def dfs(graph, v, visited):
	#현재 방문한곳 방문 처리
	visited[v] = True
    print(v, end=' ') #띄어쓰기
    #그 줄에 해당되는 배열값 방문하기
    for i in graph[v]:
    	if not visited[i]: #i의 값을 visited[i]와 비교함. 방문처리된(True)값이 아님(=False)
        	dfs(graph, i, visited)

  • 음료수 얼려먹기
    n x m 크기의 얼음틀에서 1인위치는 칸막이
    0인위치는 얼음이라고함
    먹을수있는 얼음갯수를 구하시오.
import sys

# n,m 입력받기
n,m = map(int, sys.stdin.readline().split())

# 2차원 리스트 입력받기
graph=[]
for i in range[n]:
    graph.append(list(map(int,sys.stdin().readline().split())))

def dfs(x,y):
    #상하좌우 했을때 범위를 벗어나면 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 #방문한것 1로 바뀜
        
        #상하좌우도 재귀호출. 결국 방문한것 =0 은 1이 됨
        dfs(x-1, y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False #1이면 False 반환



# 0인부분으로 꼬리에꼬리를 물어 방문한 것들을 체크함(1로 표시=false)
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            result += 1


print(result) #정답



BFS

  • 너비 우선 탐색. 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
  • 큐 자료구조 이용.
    1. 탐색시작 노드를 큐에 삽입하고 방문처리를 한다
    2. 큐에서 노드를 꺼낸 뒤, 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모든 큐에 삽입하고 방문 처리함
    3. 2번 과정을 수행할수없을때까지 반복
from collection import deque

graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]

#각 노드가 방문된 정보 표현
visited = [False] * len(graph)

#정의된 bfs함수 호출
bfs(graph, 1, visited) #1에서 시작

#dfs함수 정의
def bfs(graph, start, visited):
    queue = deque([start]) #deque의 첫번째로 큐를 넣어줌(초기:1)
    #현재 노드를 방문처리
    visited[start] = True (초기: visited[1] = True)
    #큐가 빌때까지 반복
    while queue:
    	#큐에서 하나의 원소를 뽑아 출력.
    	v = queue.popleft() #초기: v = 1
    	print(v, end=' ') #초기: 1 출력
    	#아직 방문하지 않은 인접원소를 큐에 삽입
    	for i in graph[v]:  #graph[1] => 2,3,8
    		if not visited[i]: #i의 값을 visited[2]와 비교함. visited[2]는 False이므로 True.
            #False면 방문했던거니까 패스.
        		queue.append(i) #큐에다 해당값을 대입함. 추후에 빼고 또 출력할 예정.
                visited[i] = True #지나온 자리는 방문한걸로 함.


  • n x m 미로에 갇힘. 괴물을 피해 탈출해야 함.
    나의 위치는 (1,1) 미로의 출구는 (n,m)
    한번에 한칸씩 이동가능.
    괴물이 있는 부분은 0. 괴물이 없는 부분은 1.
    탈출하기위해 움직이는 최소 칸의 갯수
from collections import deque
import sys

n,m = map(int, sys.stdin.readline().split())

graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline())))

#상 하 좌 우
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 or graph[nx][ny] == 0:
                continue
            # 괴물이 없다면 해당 노드에 +1 해서 마지막까지 +되게끔함
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1
                queue.append((nx, ny))
    return graph[n-1][m-1] #좌표가 원래 인덱스보다 +1되있어서 -1해줌

print(bfs(0,0))

스택 자료구조

  • 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조
  • 리스트 자료형을 이용.
    pop() 을 이용하면 됨
    최상단 원소부터 출력 stack[::-1]
    최하단 원소부터 출력 stack

큐 자료구조

  • 먼저 들어온 데이터가 먼저 나가는 자료구조
  • 리스트 자료형 말고 deque 이용.
    시간복잡도가 높아지지 않게 deque를 이용하자
from collection import deque

a.deque() #큐 선언. a.deque([1]) 하면 a라는 큐에 [1]이 추가된 것임.
a.append() #추가. 오른쪽에 추가.
a.popleft() #삭제. 왼쪽부터 큐가 시작되기 때문에 왼쪽부터 삭제

a.reverse() #나중에 들어온 원소부터 출력할수있게 뒤집는 법


재귀함수

  • 자기 자신을 다시 호출하는 함수
  • 반복문을 이용해 동일한 기능을 구현할 수 있다 (반복문보다 좋을수도 있고 아닐수도 있음)
  • 컴퓨터가 함수를 연속 호출시 컴퓨터 메모리 내부에 스택 프레임이 쌓임
    • 그래서 스택 사용시, 구현상 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많음
  • 제한없이 재귀함수를 호출하면 무한히 호출될수있음
    • 종료 조건을 포함해 재귀함수를 호출해야함
def function():
	if i=100:
		return #2. 함수종료
	function()

function() #1. 함수실행
#ex. 팩토리얼 구현
n! = 1 x 2 x 3 x ... x (n-1) x n

#반복적으로 구현한 n!
def factorial(n):
	result = 1
	for i in range(1, n+1):
		result *=i
	return result

#재귀적으로 구현한 n!
def factorial(n):
	if n <=1: #n이 1이하인 경우 1을 반환
		return 1
	return n * factorial(n-1)
#최대공약수 계산 (유클리드 호제법)
#- 두 자연수 A,B (A>B)에서 A를 B로 나눈 나머지가 R.
#- A와 B의 최대공약수는 B와 R의 최대공약수와 같음
#- 더 작은수를 이용해서 식을 간단히 만드는 형태

def gcd(a,b):
	if a%b == 0: #a가 b의 배수라면 b를 반환
		return b
	else:
		return gcd(b, a%b)

gcd(192,162)
저작자표시