Tree traversal
특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 함.
트리를 순회할 수 있는 세 가지 방법은 전위 순회, 중위 순회, 후위 순회임.
트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽임.
전위 순회 (preorder traverse)
중위 순회 (inorder traverse)
후위 순회 (postorder traverse)
BFS/DFS
그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적임. 그래프의 데이터는 배열처럼 정렬되어 있지 않으므로 원하는 자료를 찾으려면 하나씩 모두 방문하여 찾아야 함.
한국에서 미국으로 가는 비행기를 예약하려고 함. 비행편에 따라 직항과 경유가 잇는데, 경유를 하게 된다면 해당 항공사가 필요로 한느 공항에 잠시 머물렀다가 가기도 함. 경유하는 시간은 비행편마다 다르고 경유지도 다름. 이렇게 다양한 여정 중에서, 최단 경로를 알아내려면 어떻게 해야 할까?
BFS (Breath-First Search)
한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색함. 그리고 더는 탐색할 정점이 없을 때 그 다음 떨어져 있는 정점을 순서대로 방문함. 직항이라면 한국과 미국 사이에 어떤 경유지도 없기 때문에 제일 가까운 정점에 미국이 있음. 경유지가 있다면 직항보다 거리가 멀다는 사실을 확인할 수 있음. 이렇게 너비를 우선적으로 탐색하는 방법을 Breath-First Search, 너비 우선 탐색이라고 함. 주로 두 정점 사이의 최단 경로를 찾을 때 사용함. 만약 경로를 하나씩 전부 방문한다면 최악의 경우에는 모든 경우를 다 살펴보아야 함.
DFS (Depth-First Search)
비행기 티켓이 없다면 어떤 비행기가 미국으로 가는 것인지 알 수 없음. 이 때 비행기를 타고 여러 나라를 방문하면서, 마지막에 미국에 도착하는 경로를 찾아야함. DFS는 하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니라면 다음 경로로 넘어가 탐색함. 하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에 운이 좋다면 단 몇 번 만에 경로를 찾을 수 있음. 또 미국으로 가는 길이 아님을 미리 체크할 수 있다면, 바로 그 순간 다음 탐색으로 넘어갈 수 있음.
깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색이라 함. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용함. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있음. 만약 BFS로 탐색하게 된다면 제일 첫 번 째 경로가 미국행이더라도 다른 모든 경로를 살펴보아야 함.
DFS와 BFS는 모든 정점을 한번만 방문한다는 공통점을 가지고 잇지만 사용할 때의 장단점은 분명하게 때문에 해당 상황에 맞는 탐색 기법을 사용해야 함.
연습 문제 - 인접 행렬 찾기
문제
주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 반환해야 합니다.
import java.util.*;
public class Solution {
// 재귀를 사용한 풀이
public boolean getDirections(int[][] matrix, int from, int to) {
//2차원 배열을 선언합니다.
int[][] currentMatrix = new int[matrix.length][];
for(int i = 0; i < matrix.length; i++) currentMatrix[i] = Arrays.copyOf(matrix[i], matrix[i].length);
//입력된 출발점과 도착점이 같다면 true를 반환합니다 (재귀 함수의 도착 부분)
if(from == to) return true;
// 입력된 출발지점의 1차원 배열을 순회합니다.
for(int i = 0; i < currentMatrix[from].length; i++) {
//길이 존재한다면
if(currentMatrix[from][i] == 1) {
//해당 루트를 순회했다고 표시합니다( 1 -> 0으로 변경)
currentMatrix[from][i] = 0;
//표시된 행렬과, 출발지점을 현재 지점인 i로 변경하여 재귀함수를 실행합니다. 재귀함수가 끝까지 도달하였을때 true를 반환한 경우 true를 반환합니다.
if(getDirections(currentMatrix, i, to)) return true;
}
}
//길을 찾을수 없는 경우 false를 반환합니다.
return false;
}
// //큐를 사용한 풀이
// public boolean getDirections(int[][] matrix, int from, int to) {
// //연결 리스트를 사용하여 큐를 선언합니다.
// Queue<Integer> queue = new LinkedList<>();
// //첫 시작점으로 from을 할당합니다.
// queue.add(from);
// // 방문했다는 것을 표시하기 위해 1차원 배열을 생성합니다. 초기값은 false로 생성됩니다.
// boolean[] isVisited = new boolean[matrix.length];
// // 첫 정점 방문 여부를 표시합니다.
// isVisited[from] = true;
// // queue(방문할 곳)의 사이즈가 0이 될 때까지 반복합니다.
// while(queue.size() > 0) {
// // queue에서 정점을 하나 빼서 now에 할당합니다.
// int now = queue.poll();
// // 목적지인지 검사하고, 목적지라면 true를 반환합니다.
// if(now == to) return true;
// // 해당 정점의 간선들을 확인합니다.
// for(int next = 0; next < matrix[now].length; next++) {
// // 만약, 간선이 있고 방문하지 않았다면
// if(matrix[now][next] == 1 && !isVisited[next]) {
// // queue에 next를 넣습니다. (다음 정점으로 가기 위해)
// queue.add(next);
// // 해당 정점을 방문했다는 것을 표시합니다.
// isVisited[next] = true;
// }
// }
// }
// // 길이 없다면 false를 반환합니다.
// return false;
// }
}연습 문제 - 연결된 정점들
문제
방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.
import java.util.*;
public class Solution {
public int connectedVertices(int[][] edges) {
final int[] bigger = {0};
// 최대 버텍스를 찾습니다.
Arrays.stream(edges).forEach(data -> {
int currentBigger = Arrays.stream(data)
.boxed()
.max(Comparator.comparing(i -> i))
.orElse(0);
if(bigger[0] < currentBigger) bigger[0] = currentBigger;
});
//최대 버택스 + 1만큼의 배열을 선언합니다(0부터 시작)
int[][] adjArray = new int[bigger[0] + 1][bigger[0] + 1];
// edges를 순회하며, (무향 그래프이므로 쌍방으로) 간선을 연결해 줍니다.
for(int i = 0; i < edges.length; i++) {
int from = edges[i][0];
int to = edges[i][1];
adjArray[from][to] = 1;
adjArray[to][from] = 1;
}
// 방문한 버텍스를 담을 배열을 선언합니다.
boolean[] visited = new boolean[bigger[0] + 1];
// 컴포넌트가 몇 개인지 카운트할 변수를 선언합니다.
int count = 0;
// 방문 여부를 체크한 배열을 모두 순회합니다.
for(int vertex = 0; vertex < visited.length; vertex++) {
//만약 방문하지 않았다면
if(!visited[vertex]) {
//컴포넌트를 늘려주고
count++;
// 그래프와 버텍스, 방문했는지 확인할 visited를 bfs 혹은 dfs를 사용하여 변수에 담습니다.
visited = bfs_array(adjArray, vertex, visited);
// visited = dfs_array(adjArray, vertex, visited);
}
}
return count;
}
public boolean[] bfs_array(int[][] adjArray, int vertex ,boolean[] visited) {
//bfs의 경우 큐를 사용합니다.
Queue<Integer> queue = new LinkedList<>();
//시작지점을 큐에 넣어주고, 해당 버택스의 방문 여부를 변경합니다.
queue.add(vertex);
visited[vertex] = true;
//큐에 더이상 방문할 요소가 없을 경우까지 반복합니다.
while (!queue.isEmpty()) {
//현재 위치를 큐에서 꺼내온 후
int cur = queue.poll();
//전체 배열에서 현재 버택스의 행만 확인합니다.
for (int i = 0; i < adjArray[cur].length; i++) {
//길이 존재하고, 아직 방문하지 않았을 경우
if(adjArray[cur][i] == 1 && !visited[i]) {
//큐에 해당 버택스의 위치를 넣어준 이후
queue.add(i);
//방문여부를 체크합니다.
visited[i] = true;
}
}
}
//이어진 모든 길을 순회한 후 방문여부가 체크된 배열을 반환합니다.
return visited;
}
public boolean[] dfs_array(int[][] adjArray, int vertex ,boolean[] visited) {
//현재 버택스의 방문여부를 체크합니다.
visited[vertex] = true;
//해당 버택스의 행을 순회합니다.
for(int i = 0; i < adjArray.length; i++) {
//만약 길이 존재하고, 방문하지 않았다면
if(adjArray[vertex][i] == 1 && !visited[i]) {
//재귀를 사용하여 이어진 길부터 탐색을 다시 시작합니다.
dfs_array(adjArray, i ,visited);
}
}
//이어진 모든 길을 순회한 후 방문여부가 체크된 배열을 순회합니다.
return visited;
}
}연습 문제 - [DFS]바코드
문제
1, 2, 3으로만 이루어진 수열 바코드를 만들어야 합니다. 무조건 1, 2, 3만 붙여서 바코드를 만들었다면 쉬웠겠지만, 아쉽게도 바코드를 만드는 데에 조건이 걸려 있습니다. 바코드에서 인접한 두 개의 부분 수열이 동일하다면 제작할 수 없다고 할 때, 주어진 길이 len의 바코드 중 가장 작은 수를 반환하는 함수를 작성하세요.
import java.util.*;
public class Solution {
public String barcode(int len) {
return aux("", len);
}
public boolean isValid(String str) {
// index 관리를 편하게 하기 위해 string reverse
StringBuffer sb = new StringBuffer(str);
String reverse = sb.reverse().toString();
// 인접한 두 개의 부분 수열이 동일한지 확인한다.
// 최대 절반 길이만큼만 두 개의 부분 수열이 가능하다.
int halfLen = (int)Math.floor((double) str.length() / 2);
for(int i = 1; i <= halfLen; i++) {
if(reverse.substring(0, i).equals(reverse.substring(i, i + i))) {
return false;
}
}
return true;
}
public String aux(String str, int len) {
String chr = "123";
// 유효성을 통과해서 만든 길이 len의 str을 리턴한다.
if(str.length() == len) return str;
// 조건을 만족하는 가장 작은 수를 찾고 있으므로,
// 1, 2, 3 순서대로 검토한다.
// 실제 수(number) 비교는 필요없다.
for(int i = 0; i < chr.length(); i++) {
String currentStr = str + chr.charAt(i);
if(isValid(currentStr)) {
String founded = aux(currentStr, len);
if(founded != null) return founded;
}
}
// 현재 str에서 1, 2, 3을 이어붙여서 유효한 문자열을 만들 수 없는 경우
return null;
}
}