ol-rlo-zl
DFS(깊이우선탐색) & BFS(너비우선탐색) 본문
1. DFS ( Depth-First Search )
- 깊이 우선 탐색: 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조 ( 혹은 재귀 함수 ) 이용
- 동작과정
- 탐색 시작 노드를 스택에 삽입하고 방문처리한다. (방문기준ex: 번호가 낮은 인접 노드부터)
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리한다.
방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다. - 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
- 전체 노드의 탐색 순서 = 스택에 들어간 순서
# 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)2. BFS ( Breadth-First Search )
- 너비 우선 탐색: 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조 이용
- 활용
- 특정 조건에서의 최단 경로 문제 해결
- 각 간선의 비용이 모두 동일한 상황에서 최단 거리 문제 해결
- 동작과정
- 탐색 시작 노드를 큐에 삽입하고 방문처리한다. (방문기준ex: 번호가 낮은 인접 노드부터)
- 큐에서 노드를 꺼낸 뒤에, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
- 전체 노드의 탐색 순서 = 큐에 들어간 순서
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
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] = True3. DFS / BFS 동작 예시
- DFS의 전체 노드의 탐색 순서 (스택에 들어간 순서) : 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5
- BFS의 전체 노드의 탐색 순서 (큐에 들어간 순서) : 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited) # 1 2 7 6 8 3 4 5
# 정의된 BFS 함수 호출
bfs(graph, 1, visited) # 1 2 3 8 7 4 5 64. DFS 문제 - 음료수 얼려 먹기
문제
문제 설명
- N x M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
- 구멍이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
- 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
입력 조건
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1<=N,M<=1000)
- 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
출력 조건
- 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
입력 예시
4 5
00110
00011
11111
00000출력 예시
3풀이
# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
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
# print(graph)
# 상, 하, 좌, 우 의 위치들도 모두 재귀적으로 호출
dfs(x-1, y) # 상
dfs(x, y-1) # 좌
dfs(x+1,y) # 하
dfs(x,y+1) # 우
return True
return False
# N,M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# print(graph) # [[0, 0, 1, 1, 0], [0, 0, 0, 1, 1], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]]
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
if dfs(i,j) == True:
result += 1
print(result) # 정답 출력5. 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풀이
from collections import deque
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# BFS 소스코드 구현
def bfs(x, y):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x, y))
# 큐가 빌 때까지 반복하기
while queue:
x, y = queue.popleft()
# 현재 위치에서 4가지 방향으로의 위치 확인
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:
continue
# 벽인 경우 무시
if graph[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
# print(graph)
queue.append((nx, ny))
# 가장 오른쪽 아래까지의 최단 거리 반환
return graph[n - 1][m - 1]
# BFS를 수행한 결과 출력
print(bfs(0, 0))