View
탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.
(대표적인 탐색 알고리즘 : DFS와 BFS)
DFS (Depth-First Search, 깊이 우선 탐색) : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
1. 인접행렬 : 2차원 배열에 각 노드가 연결된 형태를 표현
- 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.
import java.util.*;
public class search_0519_02 {
public static final int INF = 999999999;
// 2차원 리스트를 이용해 인접 행렬 표현
public static int[][] graph = {
{0, 7, 5},
{7, 0, INF},
{5, INF, 0}
};
public static void main(String[] args) {
// 그래프 출력
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.print(graph[i][j] + " ");
}
System.out.println();
}
}
}0 7 5
7 0 999999999
5 999999999 0
2. 인접 리스트 : 리스트에 각 노드가 연결된 형태를 표현
- 연결된 정보만을 저장하기 떄문에 메모리를 효율적으로 사용
- 하지만 이와 같은 속성 때문에 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도는 느리다.
( 연결된 데이터를 하나씩 확인해야 하기 때문)
package search;
import java.util.ArrayList;
class Node{
private int index;
private int distance;
public Node(int index, int distance){
this.index = index;
this.distance = distance;
}
public void show(){
System.out.print("(" + this.index + "," +this.distance +") ");
}
}
public class search_0519_01 {
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
public static void main(String[] args){
for(int i=0; i<3; i++) {
graph.add(new ArrayList<Node>());
}
// 노드 0에 연결된 노드 정보 저장 (노드, 거리)
graph.get(0).add(new Node(1,7));
graph.get(0).add(new Node(2,5));
// 노드 1에 연결된 노드 정보 저장 (노드, 거리)
graph.get(1).add(new Node(0, 7));
//노드 2에 연결된 노드 정보 저장 (노드, 거리)
graph.get(2).add(new Node(0, 5));
for(int i = 0; i < 3; i++) {
for (int j = 0; j < graph.get(i).size(); j++) {
graph.get(i).get(j).show();
}
System.out.println();
}
}
}(1,7) (2,5)
(0,7)
(0,5)
DFS 동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
package search;
import java.util.ArrayList;
public class search_0601_01 {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static void dfs(int x){
visited[x] = true;
System.out.print(x + " ");
for(int i = 0; i < graph.get(x).size(); i++){
int y = graph.get(x).get(i);
if(!visited[y]) dfs(y);
}
}
public static void main(String[] args){
for(int i = 0; i < 9; i++){
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
dfs(1);
}
}
BFS (Breadth First Search, 너비 우선 탐색) : 가까운 노드부터 탐색하는 알고리즘
BFS 동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
- 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다
package search;
public class search_0601_02 {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// BFS 함수 정의
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
// 큐가 빌 때까지 반복
while(!q.isEmpty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x = q.poll();
System.out.print(x + " ");
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for(int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if(!visited[y]) {
q.offer(y);
visited[y] = true;
}
}
}
}
public static void main(String[] args) {
// 그래프 초기화
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
bfs(1);
}
}
| DFS | BFS | |
| 동작 원리 | 스택 | 큐 |
| 구현 방법 | 재귀 함수 이용 | 큐 자료구조 이용 |
1차원 배열이나 2차원 배열 또한 그래프 형태로 생각하면 수월하게 문제를 풀 수 있다.
예를 들어 게임 맵이 3 x 3 형태의 2차원 배열이고 각 데이터를 좌표라고 생각해보자.
모든 자료를 그래프의 형태로 바꿔서 생각할 수 있다. 코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 이렇게 그래프 형태로 바꿔서 생각하면 풀이 방법을 조금 더 쉽게 떠올릴 수 있다고한다. 그러므로 코딩테스트에서 탐색 문제를 보면 그래프 형태로 표현한 다음 풀이법을 고민해보자..
[출처] 나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년
728x90
'알고리즘 > 이코테' 카테고리의 다른 글
| [DFS/BFS] 이코테 미로 탈출(Java) (0) | 2022.06.07 |
|---|---|
| [알고리즘] 04. 구현 (Implementation) (0) | 2022.05.14 |
| [알고리즘] 03. 그리디 알고리즘(Greedy Algorithm) (0) | 2022.05.10 |
reply