[이코테]DFS & BFS
Coding Test 3
미리 알아야 할 자료구조
-
스택
- 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다.
- 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있다.
stack = [] stack.append(5) stack.pop() -
큐
- 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다.
- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다.
from collections import deque queue = deque() queue.append(5) queue.popleft() -
재귀함수
자기 자신을 다시 호출하는 함수
-
문제1-팩토리얼
def factorial(n) : if n <= 1 : return 1 return n * factorial(n-1) print(factorial(5)) -
문제2-최대공약수(유클리드 호제법)
def gcd(a, b) : if a % b == 0 : return b return gcd(b, a%b) print(gcd(192, 162))
1. DFS
- 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
-
스택 자료구조(혹은 재귀 함수)를 이용
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
-
동작 예시
[Step 0] 시작 노드 : 1 (방문 기준 : 번호가 낮은 인접 노드부터)
[Step 1] 시작 노드인 ‘1’을 스택에 삽입하고 방문 처리
[Step 2] 스택의 최상단 노드인 ‘1’에 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’이 있음
이중에서 가장 작은 노드인 ‘2’를 스택에 넣고 방문 처리
[Step 3] 스택의 최상단 노드인 ‘2’에 방문하지 않은 인접 노드 ‘7’이 있음
따라서 ‘7’번 노드를 스택에 넣고 방문 처리
[Step 4] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드 ‘6’, ‘8’이 있음 이 중에서 가장 작은 노드인 ‘6’을 스택에 넣고 방문 처리
[Step 5] 스택의 최상단 노드인 ‘6’에 방문하지 않은 인접 노드가 없음
따라서 스택에서 ‘6’번 노드를 꺼냄
[Step 6] 스택의 최상단 노드인 ‘7’에 방문하지 않은 인접 노드 ‘8’이 있음
따라서 ‘8’번 노드를 스택에 넣고 방문 처리
결과
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=[[], [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-음료수 얼려 먹기
N X M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주합니다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성됩니다.
입력예시
4 5
00110
00011
11111
00000
출력예시
3
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, y-1)
dfs(x+1, y)
dfs(x, y+1)
return True
return False
n, m = map(int, input().split())
graph=[]
for i in range(n) :
graph.append(list(map(int, input())))
result=0
for i in range(n):
for j in range(m):
if dfs(i, j) == True :
result += 1
print(result)
- 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 ‘0’이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문
- 방문한 지점에서 다시 상, 하, 좌, 후를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점 방문 가능
- 모든 노드에 대하여 1 ~ 2번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트
2. BFS
- 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
-
큐 자료구조를 이용
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
-
동작 예시
[Step 0] 시작 노드 : 1 (방문 기준 : 번호가 낮은 인접 노드부터)
[Step 1] 시작 노드인 ‘1’을 큐에 삽입하고 방문 처리
[Step 2] 큐에서 노드 ‘1’을 꺼내 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8’을 큐에 삽입하고 방문 처리
[Step 3] 큐에서 노드 ‘2’를 꺼내 방문하지 않은 인접 노드 ‘7’을 큐에 삽입하고 방문 처리
[Step 4] 큐에서 노드 ‘3’을 꺼내 방문하지 않은 인접 노드 ‘4’, ‘5’를 큐에 삽입하고 방문 처리
[Step 5] 큐에서 노드 ‘8’을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시
결과
from collections import deque 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=[[], [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)
문제1-미로탈출
N X M 크기의 직사각형 미로에 갇혀있습니다. 시작 위치는 (1, 1)이며 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있습니다. 이때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있습니다. 이때 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산합니다.
입력예시
5 6
101010
111111
000001
111111
111111
출력예시
10
def bfs(x, y) :
queue = deque()
queue.append((x, y))
while queue :
x, y = queue.popleft()
for i in range(4):
nx = x + d[i]
ny = y + d[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
queue.append((nx, ny))
return graph[n-1][m-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]
print(bfs(0, 0))
- (1, 1) 좌표에서 상, 하, 좌, 우로 탐색을 진행하면 바로 옆 노드인 (1, 2) 위치의 노드를 방문하게 되고 새롭게 방문하는 (1, 2) 노드의 값을 2로 바꾸게 됨
- 마찬가지로 BFS를 계속 수행하면 결과적으로 최단 경로의 값들이 1씩 증가하는 형태로 바뀐다
댓글남기기