알고리즘 문제를 풀다 보면 정말 많은 탐색 알고리즘을 요구하는 문제들을 만납니다. 먼저 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말하며, 문제에서는 주로 그래프, 트리 등의 자료구조 안에서 탐색하는 문제들이 자주 출제됩니다.
탐색 알고리즘에 들어가기에 앞서 먼저 그래프에 대해서 알아봅니다.
그래프를 표현하는 방법에는 두가지 방법이 있습니다.
public class Main {
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();
}
}
}
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 Main {
// 행(Row)이 3개인 인접 리스트 표현
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();
}
}
}
스택(Stack)은 선입후출 구조 또는 후입선출 구조의 자료구조(Data Structure)이며, 주로 구조를 박스 쌓기에 비유할 수 있습니다.
import java.util.Stack;
Stack<Integer> stack = new Stack<>();
stack.push(1); // 스택에 값 추가
stack.peek(); // 스택의 가장 상단의 값 출력
stack.pop(); // 스택의 가장 상단의 값 제거
stack.clear(); // 스택 초기화
stack.size(); // 스택의 크기 출력
stack.empty(); // 스택이 비어있는지 확인 (boolean)
stack.contains(1); // 스택에 1의 값이 있는지 확인 (boolean)
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// DFS 함수 정의
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>());
}
// 노드에 연결된 노드 정보 저장
graph.get(1).add(2);
// ... 중략 ...
graph.get(8).add(7);
dfs(1);
}
}
큐(Queue)는 흔히 큐를 대기 줄에 비유할 수 있습니다. 먼저 온 사람이 먼저 나가는 선입선출 자료구조입니다.
import java.util.LinkedList;
import java.util.Queue;
Queue<Integer> queue = new LinkedList<>(); // Integer 형 큐 선언
queue.add(1); // 큐에 값 추가
queue.offer(3); // 큐에 값 추가
queue.peek(); // 큐의 첫번째 값 출력
queue.poll(); // 큐의 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove(); // 큐의 첫번째 값 제거
queue.clear(); // 큐 초기화
public class Main {
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>());
}
// 노드에 연결된 노드 정보 저장
graph.get(1).add(2);
// ... 중략 ...
graph.get(8).add(7);
bfs(1);
}
}