탐색 (Search)
: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
그래프 탐색
: 하나의 노드를 시작으로 다수의 노드를 방문하는 것
✓ 노드 (Node) = 정점(Vertex)
: 특정 지점
✓ 간선 (Edge)
: 노드와 노드를 연결하는 선
그래프 표현 방법
1. 인접 행렬 (Adjacency Matrix)
: 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
- 연결되지 않은 노드끼리는 '무한의 비용'이라고 작성한다.
- 모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리 측면에서 비효율적이다.
- 원하는 정보를 얻기 위해서 행렬의 해당 위치만 찾으면 되기 때문에 속도가 빠르다.
## 인접 행렬 방식 예제
INF = 999999999 # 연결되지 않은 노드에 대한 무한의 비용 선언
graph = [
[0, 7, 5],
[7, 0, INf],
[5, INF, 0]]
print(graph)→ 출력
[[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]2. 인접 리스트 (Adjacency List)
: 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장하는 방식
- '연결 리스트'라는 자료구조를 이용해서 구현한다.
(C++, Java 등에서는 라이브러리 제공. Python에서는 리스트 자료형 활용) - 연결된 정보만을 젖아하기 때문에 메모리 측면에서 효율적이다.
- 원하는 정보를 얻기 위해서 연결된 데이터를 하나씩 확인해야 하기 때문에 속도가 느리다.
## 인접 리스트 방식 예제
graph = [[] for _ in range(3)]
# 노드 0에 연결된 노드 정보(노드, 거리) 저장
graph[0].append((1, 7))
graph[0].append((2, 5))
# 노드 1에 연결된 노드 정보(노드, 거리) 저장
graph[1].append((0, 7))
# 노드 2에 연결된 노드 정보(노드, 거리) 저장
graph[2].append((0, 5))
print(graph)→ 출력
[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]DFS (깊이 우선 탐색; Depth-First Search)
개념
: 그래프에서 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘
특징
스택자료구조를 이용하는 알고리즘이기 때문에 실제 구현은재귀 함수를 이용해서 더 간결하게 나타낼 수 있다.- 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.
시간복잡도
데이터의 개수가 $N$개인 경우 시간 복잡도 : $O(N)$
동작원리
탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
2번 과정을 더 이상 수행할 수 없을 때 까지 반복한다.
방문처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것
아래 그림으로 좀 더 자세히 살펴보자. 아래의 그래프에서 회색 노드는 방문 처리된 노드, 하늘색 노드는 현재 처리하는 스택의 최상단 노드이다.
위 그림을 코드로 구현해보자.
# DFS 메서드 정의
def dfs(graph, v, visited):
visited[v] = True # 현재 노드를 방문 처리
print(v, end = ' ') # 탐색된 노드 출력
for i in graph[v]: # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
if not visited[i]: # i번째 노드가 방문하지 않은 인접노드인 경우
dfs(graph, i, visited)
# 각 노드가 연결된 정보를 2차원 리스트 자료형으로 표현
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드의 방문 정보 False로 초기화 (1차원 리스트로 표현)
visited = [False] * 9
# DFS 함수 호출 (v : 최상단 노드)
dfs(graph, 1, visited)→ 출력
1 2 7 6 8 3 4 5BFS (너비 우선 탐색; Breadth-First Search)
개념
: 가까운 노드부터 탐색하는 알고리즘
특징
큐자료구조를 이용한다.- 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면, 먼저 들어온 것이 먼저 나가게 되면서 가까운 노드부터 탐색을 진행하게 된다.
- DFS와 마찬가지로 인접한 노드가 여러 개 있을 때, 숫자가 작은 노드부터 먼저 큐에 삽입한다고 가정한다.
시간복잡도
- 데이터의 개수가 $N$인 경우 시간복잡도 : $O(N)$
(일반적으로 실제 수행 시간이 DFS 보다 효율적이다.)
동작원리
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
아래 그림으로 좀 더 자세히 살펴보자. 아래의 그래프에서 회색 노드는 방문 처리된 노드, 하늘색 노드는 큐에서 꺼내 현재 처리하는 노드이다.
)
위 그림을 코드로 구현해보자.
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 # 방문처리
# 각 노드가 연결된 정보를 2차원 리스트 자료형으로 표현
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 각 노드의 방문 정보 False로 초기화 (1차원 리스트로 표현)
visited = [False] * 9
# BFS 함수 호출 (start : 시작 노드)
Bfs(graph, 1, visited)→ 출력
1 2 3 8 7 4 5 6실습
실전문제 1. 음료수 얼려 먹기 (DFS)
구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시된 N*M 크기의 얼음틀이 있다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 얼음 틀의 모양이 주어졌을 때, 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
💡 해결 아이디어
1. 특정 노드의 주변 상, 하, 좌, 우를 살펴본 뒤 주변 노드 중 값이 0이면서 아직 방문하지 않은 노드가 있다면 해당 노드를 방문한다.
2. 방문한 노드에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 노드를 방문할 수 있다.
3. 1번과 2번 과정을 모든 노드에 반복하며 방문하지 않은 노드의 개수를 센다.## 모범답안
n, m = map(int, input().split())
ice = [list(map(int, input())) for _ in range(n)]
def dfs(x, y):
# 주어진 얼음틀의 범위를 벗어나는 경우 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 현재 노드를 아직 방문하지 않았다면
if ice[x][y] == 0:
ice[x][y] = 1 # 해당 노드 방문처리
# 상,하,좌,우의 위치도 모두 재귀적으로 호출(리턴값을 사용하지 않기 때문에 단순히 연결된 모든 노드에 대해서 방문처리를 하기 위한 목적으로 수행된다)
dfs(x-1, y) # 현재 노드 기준 '왼쪽'방향 탐색
dfs(x, y-1) # 현재 노드 기준 '아래쪽'방향 탐색
dfs(x+1, y) # 현재 노드 기준 '오른쪽'방향 탐색
dfs(x, y+1) # 현재 노드 기준 '위쪽'방향 탐색
return True # 현재 위치에서 처음 DFS가 수행 => True
# 얼음틀에 1밖에 없을때 즉시 종료
return False
cnt = 0 # 카운트 할 아이스크림 개수
# 모든 노드에 대해서 음료수 채우기
for i in range(n):
for j in range(m):
if dfs(i, j) == True: # 현재 위치가 처음으로 방문처리된 노드라면
cnt += 1 # 아이스크림 개수 카운트
# 결과출력
print(cnt)→ 입력 ``` 4 5 00110 00011 11111 00000 ```
→ 출력
3📌 KEY POINT
모범답안에서 가장 헷갈렸던 부분이 바로 이 부분이었다.
cnt = 0 # 카운트 할 아이스크림 개수
# 모든 노드에 대해서 음료수 채우기
for i in range(n):
for j in range(m):
if dfs(i, j) == True: # 현재 위치가 처음으로 방문처리된 노드라면
cnt += 1 # 아이스크림 개수 카운트내가 이해가 안됐던 부분은 'dfs 메소드에 따라 방문처리된 노드가 여러개일 테고, 그렇게 되면 만들어지는 아이스크림 개수가 존재하는 노드만큼 많아지지 않을까?' 였다.
하지만 DFS 메소드 부분을 잘 살펴보면,
- DFS가 한 번 수행되면 현재 노드와 연결된 모든 노드들도 각각 확인하면서 방문처리 할 수 있도록 하고, 시작노드가 방문처리 되었다면(처음 방문하는 것이라면) 그때만 카운트하는 방식이다.
- 상,하,좌,우의 위치도 모두 재귀적으로 호출하는 부분은 리턴값을 사용하지 않기 때문에 단순히 연결된 모든 노드에 대해서 방문처리를 하기 위한 목적으로 수행된다. 즉, 시작노드에 따라서 상, 하, 좌, 우 노드 모두 따로따로 방문처리 한 리턴값을 반환하는 것이 아니라, 상, 하, 좌, 우 모두 0인 경우 연결된 시작노드에 대해서만 '대표적으로' 방문처리 한 리턴값(True 또는 1)을 반환하는 것이다.
실전문제 2. 미로 탈출
N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1,1) 이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 미로가 반드시 탈출할 수 있는 형태로 제시될 때, 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. (칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산하며, 시작 칸과 마지막 칸은 항상 1이다.)
💡 해결 아이디어
1. 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하는 방법인 BFS를 사용한다.
2. (1, 1) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다.
3. 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.## 모범답안
from collections import deque
n, m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(n)]
# 이동할 네 방향 정의 (좌, 우, 하, 상)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# bfs : 간선의 비용이 모두 같을 때 최단거리를 탐색하기 위해 사용할 수 있는 알고리즘
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 ny < 0 or nx >= n or ny >= m :
continue
# 괴물 때문이 이동할 수 없는 경우 무시
if maze[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if maze[nx][ny] == 1:
maze[nx][ny] = maze[x][y] + 1 # 바로 직전 노드에서의 최단거리값에 1을 더한 값 = 지금까지 온 최단거리
queue.append((nx, ny))
# 가장 오른쪽 아래(출구)까지의 최단 거리 반환
return maze[n-1][m-1]
# 결과출력
print(bfs(0, 0))→ 입력
5 6
101010
111111
000001
111111
111111→ 출력
10