DFS와 BFS는 그래프를 탐색하기 위한 가장 대표적인 알고리즘이다.
이번 글에서는 DFS와 BFS에 대해 정리해보고자 한다.
1. DFS
- DFS ( Depth-First Search ) 는 깊이 우선탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
- Stack 자료 구조를 사용한다. ( LIFO - 먼저 들어온 것이 가장 늦게 나감 )
- 그래프 아래까지 내려갔다가 와서 위에것들이 빠져야하기에 STACK 자료구조 사용!
- LIFO 자료구조를 갖고 있는 것이 컴퓨터의 재귀함수 처리 방식!
- 스택을 사용한 DFS의 순서는 다음과 같다
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. (2) 번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
[ TIP 1 ] 함수는 실행시, 함수 실행을 시킨 노드를 방문 처리하고, 현재 노드에서 방문하지 않은 자식 노드를 스택에 넣는다. 이후 자식 노드를 시작 노드로 실행하는 함수를 실행한다.
[ TIP 2 ] 현재 노드에서 방문하지 않은 자식 노드를 선택할 때 번호가 낮은 순서부터 처리하는 것이 코딩 테스트를 볼 때 유리?!하다.
[ DFS 구현 코드 ]
def dfs(graph, v , visited): #dfs는 스택사용
visited[v] = True # 현재노드를 방문 처리
print(v, end='')
for i in graph[v]: #현재 노드와 연결된 다른 노드를 재귀적으로 방문
if not visited[i]:
dfs(graph, i, visited)
graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited= [False] * 9
dfs(graph, 1, visited)
1-1. DFS 관련 문제! 음료수 얼려먹기
문제. N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다
입력
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
- 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
출력
- 한 번에 만들 수 있는 아이스크림 개수를 출력한다.
풀이 방법!
1. 맨 왼쪽 위부터 차례로 모두 탐색해 0인 위치를 찾으면 그 지점 기준으로 연결된 0인 부분을 모두 탐색한다.
2. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본뒤 주변 지점 중에서 값이 아직 '0'이면 방문하여 '1'로 바꾼다. ( 방문 처리)
3. 방문한 지점에서 다시 상,하,좌,우를 살펴보면서 방문을 다시 진행
4. 1~2번을 모든 노드에 반복하며 방문하지 않은 얼음의 수를 센다.
파이썬 코드!
# 음료수 얼려먹기
# Connected component를 찾는 문제
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+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)
2. BFS
- BFS ( Breadth First Search ) 는 너비 우선 탐색 으로 가까운 노드부터 탐색하는 알고리즘이다.
- 가장 먼저 들어온 것이 먼저 나가게 되므로 선입선출 방식인 큐를 사용한다.
- 큐를 사용한 BFS 동작 순서는 다음과 같다
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. (2)번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
[ BFS 구현 코드 ]
from collections import deque
def bfs(graph, start , visited): #bfs는 큐를 사용
queue=deque([start])#iterable을 인자로 건네어 초기화
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
graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited = [False]*9
bfs(graph, 1, visited)
2-1. BFS 관련 문제! 미로 탈출
문제. N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
입력
- 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다.
- 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
출력
- 첫째 줄에 최소 이동 칸의 개수를 출력한다.
입력 예시
5 6
101010
111111
000001
111111
111111
출력 예시
10
풀이 방법!
- (1,1) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다.
- BFS 메소드를 정의하여 큐에 시작점 ( i, j )를 초기에 넣어두고 큐가 빌 때 까지 반복문을 수행하도록 한다.
- 반복문을 수행할 떄마다 하나의 원소를 꺼내고 꺼낸 후 현재 위치의 상, 하, 좌, 우 방향으로 위치를 확인한다.
- 확인하는 위치가 미로 공간을 벗어나면 무시하고 해당 위치가 괴물이 있는 부분이어도 무시한다.
- 해당 위치가 이동할 수 있는 값(1)이라면 해당 위치를 처음 방문 하는 경우에만 최단 거리를 기록한다. ( 바로 직전 위치의 최단 거리 값 + 1 )
- 최종 출구의 최단 거리 값을 반환한다.
파이썬 코드!
from collections import deque
n,m = map(int, input().split())
graph=[]
for i in range(n):
graph.append(list(map(int, input())))
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 ny < 0 or nx>=n or ny>=m:
continue
if 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]
print(bfs(0,0))[ 참고자료 ]
- 도서 : 파이썬 알고리즘 인터뷰
파이썬 알고리즘 인터뷰 - 교보문고
95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트 | [이 책의 구성] [1부 코딩 인터뷰] 1장, ‘코딩 인터뷰’에서는 코딩 테스트에 대한 소개와 어떻게 하면 시험을 잘 치를 수 있을지, 문제 풀이
www.kyobobook.co.kr
'스터디IT🌼 > Algorithm' 카테고리의 다른 글
| [ 백준 15828 ] Router ( feat. 파이썬 ) (0) | 2022.05.04 |
|---|---|
| [ 백준 2346 ] 풍선 터뜨리기 ( feat. 파이썬 ) (0) | 2022.05.03 |
| [ 파이썬 ] 파이썬 자료형 별 시간 복잡도 ( BIG - O ) (0) | 2022.02.07 |
| [ 파이썬 알고리즘 인터뷰 ] 일일 온도 (0) | 2022.02.06 |
| [ 파이썬 알고리즘 인터뷰 ] 중복 문자 제거 (0) | 2022.02.03 |
댓글