DFS
- 대표적인 그래프 탐색 알고리즘 중 하나로 깊이 우선 탐색이라고 부르는 알고리즘 중 하나이다.
- 스택 자료구조 와 재귀 함수를 이용한다.
스택
- 먼저 들어온 데이터가 나중에 나가는 형식입니다 (FILO 구조)
- 입구와 출구가 동일한 형태이다.
입력 : 5-4-1-9-7-3-8-2-6
출력 : 6-2-8-3-7-9-1-4-5
재귀 함수
- 자기 자신을 다시 호출하는 함수이다.
- for 문 과 같은 반복문을 계속 함수를 통해 구현하는 방법이다.
- 단 for문과 다르게 종료 조건을 함수 내에 명시 하지 않으면 프로그램이 무한히 도는 현상이 발생 할수 있다.
def recursive(i):
if i == 100:
return
print(f'재귀 함수 {i}번 실행')
recursive(i+1)
recursive(1)DFS 동작과정
1.탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2.스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다 , 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3.2번 과정을 수행할 수 없을 떄까지 반복합니다.(재귀함수)
# DFS 는 매서드를 항상 정의 해야 한다.
# DFS 의 기본은 재귀함수를 통해 만든다.
# graph = 연결되어 있는 그래프의 정보
# v = 현재 그래프의 위치
# visited = 방문 여부
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]: #graph 별로 데이터 를
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)음료수 얼려 먹기 (DFS 예제)
- N X M 크기의 얼음 틀이 있습니다.
- 구멍이 뚫린 부분은 0 , 칸막이가 있는 부분은 1로 표시된다.
- 구멍이 뚫린 부분끼하 상 , 하 , 좌 , 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주합니다.
- 얼음 틀 모양이 주어질떄 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
해결
- DFS 에 문제중인 대표적인 예시로 블록의 칸을 이동하면서 아이스크림의 개수를 구하는 방식이다.
- 핵심은 상하좌우 방향으로 이동하는 방식을 구현해야 한다.
n, m = map(int, input().split()) # 아이스크림 틀의 크기
graph = [list(input()) for _ in range(n)] # 전체 아이스크림 틀에 그래피
visited = [[False] * m for _ in range(n)] # 해당 블록을 방문 했는지 확인하기 위해 방문
dx = [-1, 0, 1, 0] # x 좌표를 이동
dy = dx[::-1] # y좌표의 이동
def dfs(x, y):
visited[x][y] = True # 해당 노드를 방문
for i in range(4): # 상하좌우의 idx 를 탐색
nx = x + dx[i]
ny = y + dy[i]
# 아이스크림 노드를 이동시킬수 있는 조건
# 1. nx,ny 가 아이스크림 틀 안에 있어야함
# 2. nx,ny 좌표가 == 0
# 3. 한번도 방문하지 않은 0 이어야 함
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == '0' and not visited[nx][ny]:
dfs(nx, ny)
count = 0
for i in range(n):
for j in range(m):
if graph[i][j] == '0' and not visited[i][j]: # 빈 틀(0) 과 방문하지 않은 틀
print(i, j)
dfs(i, j)
count += 1
print(count)BFS
- 대표적인 그래프 탐색 알고리즘 중 하나로 너비 우선 탐색이라고 부른다.
- 큐 자료구조를 활용하는 방식이다.
큐
- 먼저 들어온 데이터가 먼저 나가는 형식의 데이터이다. (FIFO 구조)
- 큐는 입구와 출구가 모두 뚫려있는 형태로 터널과 동일한 역할이라고 생각하면된다.
- python 에서는 deque() 메서드가 queue 의 역할을 한다.
BFS 동작과정
1.탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2.큐에서 노드를 꺼낸뒤에 해당 노드와 인접한 노드중 방문하지 않는 노드를 모든 큐에 삽입하고 방문 처리를 한다.
3.더 이상 2번 과정이 수행할수 없을떄까지 반복 처리를 한다.
from collections import deque
def bfs(graph, start, visited):
# 덱을 만들어서 초기값을 지정
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 끝날떄까지 반복
while queue:
q = queue.popleft()
print(q, end=' ')
for i in graph[q]:
if not visited[i]:
queue.append(i) # queue 가 지속 되어야 하기 때문에 추가를 반드시 해주어야 한다.
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)
미로 탈출
- 두 정수 N,M 이 주어집니다.
- 다음 N개의 줄에는 M개의 정수 미로의 정보가 주어딘다. 수들은 공백 없이 붙어서 입력이 제시됩니다.
해결
-
미로 탈출 의 시작은 (0,0) 에서 시작하여 마지막 (n-1, m-1) 로 이동을 해야한다.
-
만약 (i,j) 로 이동을 한다고 하면 이전 값에서 +1 을 하여 이동 횟수를 추가해주면된다.
from collections import deque
n, m = map(int, input().split()) # 미로의 전체 모양
graph = [list(input()) for _ in range(n)] # 미로 의 전체 모양
visited = [[0] * m for _ in range(n)] # 미로의 방문 순서
dx = [-1, 0, 1, 0] # 상,하,좌,우 x변경
dy = dx[::-1] # 상,하,좌,우 y 변경
def bfs(x, y):
queue = deque([]) # BFS 를 하기위한 큐를 생성
queue.append((x, y)) # 큐에서 초기값 (x,y) 를 삽입
visited[x][y] = 1 # 해당 노드가 시작점이기 때문에 1로 초기화
while queue:
x, y = queue.popleft() # 큐 에서 값을 제거
for i in range(4): # 상,하,좌,우 위치로 이동할수 있도록 이동
nx = x + dx[i]
ny = y + dy[i]
#좌쵸 이동 조건
#1.해당 nx,ny 가 graph 안에 있어야 함
#2.해당 좌표가 이동할 수 있어 야 한다 == 1
#3.만약에 해당 노드가 방문 하지 않았으면 방문 처리해야 하기 때문에 == 0
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == '1' and visited[nx][ny] == 0:
queue.append([nx, ny])
visited[nx][ny] = visited[x][y] + 1
bfs(0, 0)
print(visited[n - 1][m - 1])
개발자 되고 싶어요