DFS
깊이 우선 탐색 알고리즘인 DFS는 특정 경로를 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아와서 다른 경로를 탐색하는 방식이다.
스택 자료구조를 이용한다.
DFS 구현 방식
1.
탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2.
스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3.
2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다 → ‘재귀 함수’ 사용
‘방문 처리’ 는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다.
일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면, 번호가 낮은 순서부터 처리한다.
구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다
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)
# 인접 리스트 graph
graph = [
[],
[2,3,8], # 1번 노드
[1,7], # 2번 노드
[1,4,5], # 3번 노드
[3,5], # 4번 노드
[3,4], # 5번 노드
[7], # 6번 노드
[2,6,8] # 7번 노드
[1,7] # 8번 노드
]
visited = [False] * 9
# 함수 호출 - 방문을 한 노드 순서대로 나옴
dfs(graph, 1, visited)
Python
복사
BFS
너비 우선 탐색이라고 부른다. 가까운 노드부터 탐색하는 알고리즘이다.
BFS 구현은 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다.
BFS 구현 방식
1.
탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2.
큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3.
2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
DFS와 동일하게 인접한 노드가 여러 개 있을 때, 숫자가 작은 노드부터 먼저 큐에 삽입한다고 가정한다.
실제 수행 시간은 DFS보다 좋은 편이라고 한다.
BFS - 코드 예시
from collections import deque
# BFS
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
# graph
graph = [
[],
[2,3,8], # 1번 노드
[1,7], # 2번 노드
[1,4,5], # 3번 노드
[3,5], # 4번 노드
[3,4], # 5번 노드
[7], # 6번 노드
[2,6,8] # 7번 노드
[1,7] # 8번 노드
]
visited = [False] * 9
# 함수 호출
bfs(graph, 1, visited)
Python
복사
음료수 얼려 먹기 - DFS
N X M 크기의 얼음 틀이 있음. 구멍이 뚫려 있는 부분이 0, 칸막이가 1임.
구멍이 뚫려있는 부분에서의 상하좌우로 붙어 있는 경우에 서로 연결되어 있는 것으로 판단.
얼음 틀의 모양이 주어졌을 때, 생성되는 아이스크림의 총 개수를 구하시오.
[ 구현 flow ]
•
특정 지점 주변 상,하, 좌, 우를 살펴본 다음 주변 지점 중에서 값이 0이고 아직 방문하지 않은 경우에 해당 지점을 방문한다.
•
방문한 지점에서 다시 상,하, 좌, 우를 살펴보면서 방문을 연달아 진행한다.
•
위의 과정을 반복하면서 방문하지 않은 지점의 수를 센다.
# DFS
# 음료수 얼려 먹기
# 0이 구멍칸, 1이 칸막이칸
# n, m 은 각각 세로길이와 가로길이
n,m = map(int, input().split())
# 얼음 틀 생성 - 2차원 리스트
graph = []
for _ in range(n):
graph.append(list(map(int, input())))
# 1. 특정 지점의 주변 상,하,좌,우를 살피면서 값이 0이고, 방문하지 않은 경우 방문한다
# 2. 옮긴 지점에서 다시 1을 반복하면서 진행한다
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):
dfs(i,j) == True:
result += 1
print(result)
Python
복사
미로 탈출
# BFS
# n,m은 미로의 세로, 가로 길이다
# 0은 괴물이 있는 부분, 1이 괴물이 없는 부분
# 시작칸과 마지막칸은 항상 1이다
# 최소 이동 칸의 개수를 출력한다
from collections import deque
n,m = map(int, input().split())
# 맵의 정보를 입력받는다
graph = []
for _ 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)) # (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
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))
Python
복사
특정 거리의 도시 찾기
############# bfs #############
# 특정 거리의 도시 찾기
# 특정한 도시 X로부터 출발 , 최단 거리가 K인 모든 도시의 번호를 출력
# 1~N번까지의 도시, M개의 단방향 도로
# 첫째줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 번호 X가 주어짐
# 둘째줄부터 M개의 줄에 걸친 A번 도시에서 B번 도시로 이동하는 단방향 도로가 입력
# 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력
# 만약 하나도 존재하지 않으면 -1 출력
from collections import deque
n,m,k,x = map(int, input().split())
graph = [[] for i in range(n+1)]
visited = [False]*(n+1)
distance = [0]*(n+1) # 각각의 위치로의 거리를 저장하기 위한 변수
for i in range(m):
a,b = map(int, input().split())
graph[a].append(b)
def bfs(start):
answer = []
q = deque([start]) # 큐에 현재 위치 삽입
visited[start] = True # 방문처리
distance[start] = 0 # 첫 위치 거리 = 0
while q: # 큐에 값이 없으면 탈출
now = q.popleft()
for i in graph[now]:
if not visited[i]: # 아직 방문하지 않았으면
visited[i] = True # 방문 처리
q.append(i)
distance[i] = distance[now] + 1 # 현재 위치에서 + 1한 거리를 인접 위치거리에 할당
if distance[i] == k:
answer.append(i)
if len(answer) == 0:
print(-1)
else:
answer.sort()
for i in answer:
print(i, end='\n')
bfs(x)
Python
복사