목차
- 꼭 필요한 자료구조 기초 124
- 탐색 알고리즘 DFS/BFS 134
- [실전 문제] 음료수 얼려 먹기 149
- [실전 문제] 미로 탈출 152
꼭 필요한 자료구조 기초
- 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
- 대표적인 그래프 탐색 알고리즘 : DFS(Depth First Search), BFS(Breadth First Search)
- 자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조
- 삽입(Push), 삭제(Pop)
- 스택, 큐를 사용할 경우 삽입, 삭제 이외에도 overflow, underflow 고려 필요
- 오버플로(Overflow) : 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 경우 발생
- 언더플로(Underflow) : 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산 수행 시 발생
책에서는 파이썬으로 내용을 다루지만, 자바 기준으로 포스팅하겠습니다.
- 스택(Stack)
- 선입후출(First In Out), 후입선출(Last In Frirst Out)
- stack.push() : 스택에 원소를 삽입한다.
- stack.pop() : 스택의 맨 위의 원소를 삭제한다.
- stack.peek() : 스택의 맨 위의 원소를 출력한다.
- stack.size() : 스택의 크기 출력
- stack.empty() : 스택이 비어있는지 확인
- stack.contains() : 함수 안에 있는 인자 값이 스택에 포함되어 있는지 확인
- stack.clear() : 스택에 있는 모든 데이터를 한 번에 삭제한다.
- 큐(Queue)
- 선입선출(First In First Out)
- queue.offer() : 큐에 원소를 삽입
- queue.pool() : 큐에서 제일 처음(맨 앞)에 넣은 값을 삭제
- queue.peek() : 값을 삭제하지 않고, 맨 앞의 값을 출력
- 재귀 함수(Recursive Function)
- 자기 자신을 다시 호출하는 함수
- 프랙털(Fractal) 구조와 흡사 : 시에르핀스키 삼각형
- 종료 조건을 꼭 명시해야 한다.
- 재귀 함수는 내부적으로 스택 자료구조와 동일하다.
- ex. factorial : 반복문보다 재귀 함수를 사용한 이점은?
탐색 알고리즘 DFS/BFS
- 그래프
- 노드(Node) = 정점(Vertex)
- 간선(Edge)
- 그래프 표현 방식 2가지
- 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계 표현
- 인접 리스트(Adjacency List) : (연결)리스트로 그래프의 연결 관계 표현
그래프 표현 1 - 인접 행렬
그래프 표현 2 - 인접 리스트
- 인접 행렬 vs 인접 리스트
- 인접 행렬 : 모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리 낭비
- 인접 리스트 : 연결된 정보만 저장하기 때문에 메모리 효율적, but 조회 속도 저하
- 그래프 탐색
- 하나의 노드를 시작으로 다수의 노드를 방문하는 것
- 두 노드가 간선으로 연결 = 두 노드는 인접하다(Adjacent)
- DFS(Depth-First Search) 깊이 우선 탐색
- 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드 방문 후, 돌아가서 다른 경로 탐색
- 데이터 개수가 N개일 경우 시간복잡도 : O(N)
- 재귀함수 이용
- 재귀 함수는 스택구조와 동일하지만, 실제로 스택을 사용하지는 않는다.(Stack Overflow)
- 활용 문제
- 백트래킹, 위상 정렬
- 백트래킹 : 해를 찾는 도중, 찾는 해가 아닐 경우 되돌아가서 해를 찾는 방법
- 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드(white)가 있으면 그 인접 노드를 스택에 넣고 방문 처리(gray)를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. (방문하지 않은 노드가 여러 개일 경우 번호가 낮은 순서부터 처리)
- 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
- 노드의 탐색 순서(스택에 들어간 순서) 1->2->7->6->8->3->4->5
DFS 예제
- BFS(Breadth First Search) 너비 우선 탐색
- 가까운 노드부터 탐색하는 알고리즘
- 시간복잡도 : O(N), 일반적인 경우 실제 수행 시간은 DFS보다 빠르다.
- Queue 이용(선입 선출 방식)
- 활용 문제
- 동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다. (인접한 노드가 여러 개일 경우, 숫자가 작은 노드부터 먼저 큐에 삽입)
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
- 노드의 탐색 순서(큐에 들어간 순서) 1->2->3->8->7->4->5->6
BFS 예제
- 1차원 배열과 2차원 배열은 그래프의 형태로 바꿔서 생각할 수 있다. (단, 상하좌우로만 이동하는 경우)
- DFS, BFS는 배열로 풀이 가능
실전 문제 (1)
- 문제 요약
- N X M 크기의 얼음 틀
- 구멍 0, 칸막이 존재 1
- 상하좌우로 붙어 있는 경우 연결되어(두 노드가 간선으로 연결) 있는 것으로 간주
- 생성되는 아이스크림 개수 구하기
- 위의 문제의 출력 값은 3
- 문제 해설
- 그래프에서 묶음을 찾아주는 프로그램은 어떻게 작성? -> DFS 사용
- 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
- 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문 가능
- 1~2번의 과정을 모든 노드에 반복하여 방문하지 않은 지점의 수를 센다.
실전 문제(2)
- 문제 요약
- N X M 크기의 미로
- 현재 위치(1, 1)
- 출구 위치(N, M)
- 괴물이 있는 부분 0, 괴물이 없는 부분 1
- 최소 이동 칸의 개수 구하기(시작, 마지막 칸 포함)
- 문제 해설
- 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드 탐색. 최단 거리 -> BFS 사용
- (1, 1) 부터 모든 노드의 값을 거리 정보로 넣는다.
- 특정 노드에 방문할 때 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.
출발 지점에서 출구 까지 BFS 수행한 결과
<참고> DFS와 BFS 시간 복잡도
인접 행렬 : O(N^2)
인접 리스트 : O(N+E)