1. DFS(Depth-First Search)
깊이우선탐색, 인접노드를 stack 자료구조에 넣는다는 것이 핵심.
- 탐색노드를 stack에 넣은 후 추출하여 방문처리한다.
- 이후 해당 탐색노드의 인접노드 중 방문하지 않은 노드만 stack에 넣는다.
- stack에 넣은 노드를 추출하여 방문처리, 그 노드의 인접노드 중 방문하지 않는 노드에 대해 stack에 넣고 위 과정을 반복한다.
1-1. dfs graph 및 예시
최초 시작점은 1로 잡고, 이에 대한 dfs를 한다고 가정하였을때의 알고리즘은 아래와 같다.
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
def dfs(graph, v, visited):
visited[v] = True
print(v, end='')
for node in graph[v]:
if visited[node] is False:
dfs(graph, node, visited)
dfs(graph, 1, visited)1-2. 얼음이 뚫려있는 구간 찾기
#graph 형태로 모델링할 수 있다면 1차 의심
#노드의 인접노드, 이어진 관계를 파악해야 한다면 2차의심
N * M 크기의 얼음틀이 있다.
구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 나타낸다.
구멍이 뚫려있는 부분끼리 상,하,좌,우 한 부분이라도 연결되어있다면 하나의 얼음으로 간주한다.
얼음 틀 모양이 주어졌을때, 생성되는 구멍뚫린 얼음의 총 개수를 구하는 알고리즘은?
- 첫째줄에 얼음 틀의 세로 길이(N행), 얼음 틀의 가로 길이(M열)가 입력된다.
- 둘째줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
## 먼저 값이 0이면서 방문하지 않은 특정지점에서 부터 시작
## 특정 지점의 상, 하, 좌, 우를 살펴 인접 지점에서 방문하지 않은 지점이 있다면 방문
## 해당 방문 지점에서 인접노드를 살펴보고 방문, 이 과정을 반복
## 방문하지 않은 0의 지점 수를 카운트.
#기본 입력(공백기준)
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
#입력받은 값을 배열(리스트) 형태로 저장후 graph정보에 넣기
graph.append(list(map(int, sys.stdin.readline().split())))
#dfs
#인접노드를 계속해서 파고들면서 파악하므로 dfs
def dfs(i, j):
#먼저 범위 밖이면 dfs 종료
if i < 0 or i >= n or j < 0 or j >= m:
return False
if graph[i][j] == 0:
# 방문하고
graph[i][j] == 1
#그 인접노드까지 모두 방문이 종료되어야, 모든 알고리즘을 종료
dfs(i-1,j)
dfs(i,j-1)
dfs(i+1,j)
dfs(i,j+1)
return True
else: #graph 지점이 1인 경우엔 pass
pass
return False
result = 0
for i in range(n):
for j in range(m):
if dfs(i, j) == True:
result = result + 1
2. BFS(Breadth-First Search)
너비우선탐색, 인접노드를 Queu 자료구조에 넣는다는 것이 핵심.
- 탐색노드를 Queue에 넣고, 추출하여 방문처리한다.
- 해당 탐색노드의 모든 인접노드를 Queue에 넣는다.
※이때 모든 인접노드를 Queue에 넣는다는 개념은, 해당 노드를 출발하여 지나갈 수 있는 모든 노드를 삽입하는 것을 의미한다(=경로탐색) - Queue에 존재하는 노드를 추출하면서 방문처리, 인접노드를 Queue에 넣는 과정을 반복한다.
2-1. bfs graph 및 예시
최초 시작점을 1로 잡고, 1을 출발하여 너비탐색할 수 있는 모든 경우의 수를 도출하는 과정은 아래와 같다.
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
from collections import deque
#queue 자료구조는 반드시 queue 라이브러리를 사용
def bfs(graph, v, visited):
#queue 최초 선언
queue = deque([v])
visited[v] = True
while queue:
v = queue.popleft()
print(v, end='')
for node in graph[v]:
if visited[node] is False:
queue.append(node)
visited[node] = True
bfs(graph, 1, visited)2-2. 미로찾기
탐색할 수 있는 모든 경로, 최단경로 등에 대해서는 bfs(인접노드를 모두 추가하는 과정이 모든 경로를 탐색하는 과정을 의미)를 적용한다.
key point : 노드를 방문할때마다 누적 노드만큼 counting
통과할 수 있는 경로를 탐색하면서, 각 노드에 거쳐진 노드 수를 count하면서 최소 경로를 찾는다.
bfs 적용하기
N * M 크기의 직사각형 형태 미로가 있다고 하자.
현재 위치는 1,1이고 미로의 출구는 N,M이다.
미로를 통과할 수 없는 부분을 0, 통과할 수 있는 부분을 1이라 할 때,
미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하는 알고리즘은?
- 간선의 비용이 모두 같은 상황에서 최단거리를 구하고 싶다면
- BFS
- 특정 노드를 방문하였을때 상하좌우가 모두 인접노드가 되고
- 이때 통과할 수 있는 노드를 Queue에 넣는다.
#기본 입력
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
graph.append(list(map(int, sys.stdin.readline().split())))
#상 하 좌 우
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 nx > n-1 or ny < 0 or ny > m-1:
continue #아래 구문을 무시하고 다음 반복을 실행
if nx ==0 and ny == 0:
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))3. 참조자료
recursion error 관련
https://help.acmicpc.net/judge/rte/RecursionError
