💡 그래프 (Graph) - 비선형 구조 중 하나로 ‘정점(Vertices)과 그들 사이를 연결하는 간선(Edge)으로 표현된 자료구조’를 의미합니다. 각 정점은 데이터를 저장하며 간선은 정점들 간의 관계를 나타냅니다.
- 모든 그래프는 공식적으로 정점(V)과 간선(E)으로 그래프는 G = {V, E}로 표현이 됩니다. - 그래프는 다양한 형태와 용도를 가지며 네트워크, 경로 탐색, 스케줄링 등 다양한 시스템에서 활용됩니다. - 또한 다양한 알고리즘과 연산을 수행하는데 이용됩니다. 예를 들어 그래프 탐색 알고리즘을 사용하여 특정 노드를 찾거나 최단 경로 알고리즘을 사용하여 두 노드 사이의 최단 경로를 찾을 수 있습니다
- 그래프 탐색 알고리즘 중 하나로 한 방향으로 갈 수 있을 때까지 최대한 깊게 탐색한 후 더 이상 갈 수 없게 되면, 다시 돌아와 다음 경로를 탐색하는 방식을 의미합니다.
- 기본적인 수행과정은 한 노드에서 시작하여 가능한 한 깊숙이 탐색한 후, 다음 분기로 넘어갑니다. 그리고 더 이상 탐색할 수 없는 상태에 도달하면, 이전으로 돌아가서 다른 가능한 분기를 탐색합니다. - ‘모든 정점을 방문’하고 연결된 모든 간선을 검사하기 때문에 그래프의 모든 구성 요소를 탐색(완전 탐색)하거나 특정 조건을 만족하는 경로를 찾을 때 유용합니다.
💡 [참고] 깊이 우선 탐색에 사용되는 주요 용어에 대해 알아봅니다.
용어
설명
그래프(Graph)
정점과 간선의 집합으로 구성되어 있으며 정점은 서로 다른 정점과 연결된 구조를 가지는 형태를 의미합니다.
정점 (Vertices)
그래프에서 ‘데이터’를 나타내는 개별 요소를 말합니다. 노드(Node)라고도 불립니다.
간선(Edge)
그래프에서 ‘정점간의 관계’를 나타내는 선입니다. 연결선이라고도 불립니다.
분기(Branching)
특정 노드에서 후퇴하기 전에 가능한 모든 경로를 탐색하는 과정을 의미합니다.
방문한 노드(Visited Node)
이미 탐색되어 처리된 정점을 의미합니다.
미 방문 노드(Unvisited Node)
아직 탐색되지 않은 정점을 의미합니다.
인접한 노드(Adjacent Node)
그래프에서 특정한 노드와 연결된 노드를 의미합니다. 즉, 어떤 노드와 간선(edge)으로 직접 연결되어 있는 다른 노드들을 말합니다.
1. 깊이 우선 탐색(DFS)의 주요 특징
💡 깊이 우선 탐색(DFS)의 주요 특징 1. 깊이 우선 탐색 방법 - 스택(Stack) 또는 재귀(Recursion)를 사용하여 구현할 수 있습니다. - 탐색을 시작한 정점을 스택에 push하고, 해당 정점과 연결된 정점들을 차례로 방문합니다. - 그래프의 구조를 재귀적으로 탐색하므로, 재귀 호출을 사용하는 경우 스택 오버플로우에 유의해야 합니다.
2. 탐색 과정 - 깊이우선 탐색은 한 정점에서 시작하여 최대한 깊게 탐색한 후, 더 이상 방문할 수 있는 정점이 없을 경우 이전 정점으로 돌아와 다른 경로로 탐색합니다. 이 과정을 반복하여 그래프의 모든 정점을 탐색합니다.
3. 경로의 길이를 고려하지 않습니다. - 최단 경로를 찾는 문제와는 다르게, 경로의 길이를 고려하지 않습니다. - 탐색을 시작한 정점에서부터 가능한 한 깊이까지 탐색하기 때문에, 최단 경로를 찾는 문제에는 다른 알고리즘을 사용해야 합니다.
4. 구현이 간단합니다. - 깊이우선 탐색은 재귀적인 특성을 가지고 있어 구현이 간단합니다. - 하지만 그래프의 깊은 부분을 탐색할 경우에는 스택 오버플로우(Stack Overflow)가 발생할 수 있으므로, 반복적인 구현이 필요할 수도 있습니다.
2. 깊이 우선 탐색(DFS) 구현방법
💡 깊이 우선 탐색(DFS) 구현방법
- 깊이 우선 탐색은 재귀(Recursion)나 스택(Stack)을 통해 구현할 수 있습니다. - 구현 방법은 프로그래머스의 문제를 기반으로 구현방법에 대해 알아봅니다.
2.1. 재귀함수를 이용한 구현방법
💡 깊이 우선 탐색을 '재귀 함수'로 구현하는 방법 - 프로그래머스의 ‘피로도’와 '타겟 넘버'라는 문제를 기반으로 재귀를 이용하여 DFS를 구현하는 방법에 대해 알아봅니다.
💡 프로그래머스 피로도 - 깊이 우선 탐색 알고리즘(DFS)에서 재귀함수를 통하여 해결하는 방법
- 메인 함수에서는 dfs() 함수를 재귀적으로 호출하여 해당 함수에서는 던전의 방을 방문하여 피로도를 계산하는 역할을 합니다.
- 주어진 피로도(k)와 dungeons 배열을 이용하여 방문 가능한 ‘모든 경우의 수를 탐색’합니다. - 방문한 방을 체크하고, 재귀적으로 다음 방을 방문하며 피로도를 감소시키고 카운트를 증가시킵니다. 탐색이 완료되면 최대 카운트 값을 계산하여 max 변수에 저장합니다.
static boolean[] visited;
static int max = 0;
/**
* 17. [완전탐색 DFS] 피로도
*
* @return ResponseEntity
* @link ...
* @since 2023.11.25
*/
@GetMapping("/exhausSearch5")
public ResponseEntity<apiresponse> question17() {
int answer = 0;
int k = 80;
// 최소 피로도, 소모 피로도
int[][] dungeons = {{80, 20}, {50, 40}, {30, 10}};
// [STEP1] visited 방문한 방을 체크합니다.(던전과 동일한 사이즈로 지정합니다)
visited = new boolean[dungeons.length];
// [STEP2] dfs 함수에 값들을 전달합니다. (* cnt: 방에 방문한 횟수를 체크합니다)
dfs(k, dungeons, 0);
answer = max;
ApiResponse ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
/**
* 던전의 방을 방문하며 Counting 수행합니다.
*
* @param k 현재 피로도
* @param dungeons 던전 정보
* @param cnt 방에 방문한 횟수
*/
void dfs(int k, int[][] dungeons, int cnt) {
// [STEP1] 모든 던전을 순회합니다.
for (int i = 0; i < dungeons.length; i++) {
int visitFatigue = dungeons[i][0]; // 방문에 필요한 최소 필요도
int recoverFatigue = dungeons[i][1]; // 방문후 회복되는 피로도
// [STEP2] 기존에 방문 확인, 최소 피로도 확인
if (visited[i] || k < visitFatigue) {
continue;
}
// [STEP3] 방문함을 지정합니다.
visited[i] = true;
// [STEP4] 재귀적으로 현재 피로도를 제외하여 호출합니다.
dfs(k - recoverFatigue, dungeons, cnt + 1);
// 다른 케이스를 위해 방문 취소
visited[i] = false;
}
// 최대 카운트를 계산합니다.
max = Math.max(max, cnt);
}
💡 프로그래머스 타겟 넘버 - 깊이 우선 탐색 알고리즘(DFS)에서 재귀함수를 통하여 해결하는 방법 -2
- 해당 DFS는 재귀함수 형태로 구성이 되었습니다. - numbers 배열 내의 더하거나 빼서 타깃넘버를 만들려고 할 때, 아래와 같은 방법을 사용하여 구현합니다. - '+'를 하는 경우는 왼쪽으로 이동하고 -를 하는 경우는 오른쪽으로 이동을 합니다.
💡 너비 우선 탐색(BFS, Breadth-First Search) - 그래프 탐색 알고리즘 중 하나로 루트 노드에서 시작하여 인접한 모든 노드를 우선 탐색하여 모든 정점을 탐색하는 데 사용되는 방식을 의미합니다. 이때 인접한 노드는 너비를 우선적으로 탐색합니다.
- 순서 탐색(Level Order Traversal)이라고도 불리며, 그래프의 모든 노드를 방문하는 데 사용될 수 있습니다. - BFS는 큐를 사용하여 구현됩니다. 시작 정점을 큐에 넣고, 큐에서 하나의 정점을 꺼내서 인접한 정점들을 큐에 넣는 과정을 반복합니다. 이렇게 큐를 사용하여 탐색을 진행하면, 먼저 방문한 정점들부터 순서대로 탐색하게 됩니다. BFS는 최단 경로 문제를 해결하는 데에도 사용될 수 있습니다. - 예를 들어, 두 정점 사이의 최단 경로를 찾을 때 BFS를 사용하여 탐색하면, 시작 정점에서 목표 정점까지의 최단 경로를 찾을 수 있습니다.
1. 너비 우선 탐색(BFS)의 주요 특징
💡 너비 우선 탐색(BFS)의 주요 특징
1. 레벨 단위로 탐색합니다.
- 루트 노드에서 시작하여 레벨 단위로 탐색을 진행하며 같은 레벨에 있는 노드를 모두 탐색한 다음에야 다음 레벨로 이동합니다.
2. 큐를 사용하여 구현이 됩니다.
- 시작 정점을 큐에 넣고, 큐에서 하나씩 정점을 꺼내며 인접한 정점들을 방문하는 방식으로 동작을 합니다.
3. 그래프의 모든 정점을 방문할 수 있습니다.
- 네트워크, 그래프 등 다양한 데이터 구조에서 사용될 수 있으며, 모든 정점을 방문하여 탐색할 수 있습니다.
4. 최단 경로 문제를 해결하는데에도 사용될 수 있습니다.
- 시작 정점에서 목표 정점까지의 최단 경로를 찾을 때 BFS를 사용하여 탐색하면, 가까운 정점들부터 탐색하기 때문에 최단 경로를 찾을 수 있습니다.
2. 너비 우선 탐색(BFS) : 구현방법
💡너비 우선 탐색(BFS) 구현방법
- 너비 우선 탐색(BFS)는 '큐(Queue)'를 통해 구현할 수 있습니다. - 구현 방법은 프로그래머스의 문제를 기반으로 구현방법에 대해 알아봅니다.
2.1. 큐를 이용한 구현방법
💡프로그래머스 타겟 넘버 - 너비 우선 탐색 알고리즘(BFS)에서 '큐'를 통하여 해결하는 방법 -1
- 프로그래머스의 ‘타겟 넘버’라는 문제를 기반으로 큐를 이용하여 BFS를 구현하는 방법에 대해 알아봅니다.
- 아래의 그림과 같이 너비 탐색을 수행합니다. - 수행을 하다가 index와 number의 길이가 같으면서, 현재 합과 타겟이 되는 값이 같으면 Count를 하여 타겟의 값을 구성한 경우를 카운팅 합니다. - 주어진 numbers 배열의 각 요소를 더하거나 빼서 target과 동일한 값을 만들 수 있는 경우의 수를 계산하기 위해 너비 우선 탐색(BFS) 알고리즘을 사용합니다. - 큐를 사용하여 각 단계에서 가능한 모든 경우의 수를 탐색하고, 조건을 만족하는 경우 answer 변수를 증가시킵니다.
/**
* 17. [완전탐색] 타겟넘버
*
* @return ResponseEntity
* @link ...
* @since 2023.11.25
*/
@GetMapping("/exhausSearch5")
public ResponseEntity<apiresponse> question18() {
int[] numbers = {1, 1, 1, 1, 1};
int target = 3;
int answer = 0;
Queue queue = new LinkedList<>();
queue.offer(new Pair(0, 0)); // (currentSum, index)
while (!queue.isEmpty()) {
Pair pair = queue.poll();
int currentSum = pair.currentSum;
int index = pair.index;
if (index == numbers.length) {
if (currentSum == target) {
answer++;
}
} else {
queue.offer(new Pair(currentSum + numbers[index], index + 1)); // 현재 합계 값의 더한 수(+)를 큐에 추가합니다.
queue.offer(new Pair(currentSum - numbers[index], index + 1)); // 현재 합계 값의 뺀 수(-)를 큐에 추가합니다
}
}
ApiResponse ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
class Pair {
int currentSum;
int index;
public Pair(int currentSum, int index) {
this.currentSum = currentSum;
this.index = index;
}
}
