이번 장에서는 깊이우선탐색(DFS)과 넓이우선탐색(BFS)를 활용하여 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.
이진트리 순회(깊이우선탐색)
아래 그림과 같은 이진트리를 탐색하세요.
전위순회 출력: 1 2 4 5 3 6 7
중위순회 출력: 4 2 5 1 6 3 7
후위순회 출력: 4 5 2 6 7 3 1
public class BinaryTreeSearchDFS {
private final List<Integer> frontSearch = new ArrayList<>();
private final List<Integer> midSearch = new ArrayList<>();
private final List<Integer> rearSearch = new ArrayList<>();
static class Node {
int data;
Node leftSon;
Node rightSon;
public Node(int data) {
this.data = data;
}
}
// 전위순회
public void solution1(Node root) {
if (Objects.nonNull(root)) {
frontSearch.add(root.data);
solution1(root.leftSon);
solution1(root.rightSon);
}
}
// 중위순회
public void solution2(Node root) {
if (Objects.nonNull(root)) {
solution2(root.leftSon);
midSearch.add(root.data);
solution2(root.rightSon);
}
}
// 후위순회
public void solution3(Node root) {
if (Objects.nonNull(root)) {
solution3(root.leftSon);
solution3(root.rightSon);
rearSearch.add(root.data);
}
}
@Test
@DisplayName("이진트리 순회(깊이우선탐색)")
public void main() {
Node root = new Node(1);
root.leftSon = new Node(2);
root.rightSon = new Node(3);
root.leftSon.leftSon = new Node(4);
root.leftSon.rightSon = new Node(5);
root.rightSon.leftSon = new Node(6);
root.rightSon.rightSon = new Node(7);
solution1(root);
solution2(root);
solution3(root);
Integer[] expectedAnswer1 = {1, 2, 4, 5, 3, 6, 7};
Integer[] expectedAnswer2 = {4, 2, 5, 1, 6, 3, 7};
Integer[] expectedAnswer3 = {4, 5, 2, 6, 7, 3, 1};
assertArrayEquals(expectedAnswer1, frontSearch.toArray());
assertArrayEquals(expectedAnswer2, midSearch.toArray());
assertArrayEquals(expectedAnswer3, rearSearch.toArray());
}
}부분집합 구하기(DFS)
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.
- 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다. - 출력설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다. - 입력예제 1
3 - 출력예제 1
1 2 3
1 2
1 3
1
2 3
2
3 - 해설
public class FindSubsetDFS {
private final List<Integer[]> answer1 = new ArrayList<>();
private final int number = 3;
private final Integer[] checkArray = new Integer[number + 1];
public void solution1(int tempNumber) {
if (tempNumber == number + 1) {
List<Integer> tempList = new ArrayList<>();
for (int i = 1; i <= number; i++) {
if (Objects.nonNull(checkArray[i]) && checkArray[i] == 1) {
tempList.add(i);
}
}
if (tempList.size() > 0) {
answer1.add(tempList.toArray(new Integer[0]));
}
} else {
checkArray[tempNumber] = 1;
solution1(tempNumber + 1);
checkArray[tempNumber] = 0;
solution1(tempNumber + 1);
}
}
@Test
@DisplayName("부분집합 구하기(DFS)")
public void main() {
Integer[][] expectedAnswer1 = {
{1, 2, 3},
{1, 2},
{1, 3},
{1},
{2, 3},
{2},
{3}
};
solution1(1);
assertArrayEquals(expectedAnswer1, answer1.toArray());
}
}이진트리 순회(넓이우선탐색: 레벨탐색)
아래 그림과 같은 이진트리를 탐색하세요.
레벨 탐색 순회 출력: 1 2 3 4 5 6 7
public class BinaryTreeSearchBFS {
List<Integer> answer = new ArrayList<>();
static class Node {
int data;
Node leftSon;
Node rightSon;
public Node(int data) {
this.data = data;
}
}
public void solution1(Node root) {
Queue<Node> queueOfNode = new LinkedList<>();
queueOfNode.offer(root);
while (!queueOfNode.isEmpty()) {
for (int i = 0; i < queueOfNode.size(); i++) {
Node tempNode = queueOfNode.poll();
answer.add(tempNode.data);
if (Objects.nonNull(tempNode.leftSon)) {
queueOfNode.offer(tempNode.leftSon);
}
if (Objects.nonNull(tempNode.rightSon)) {
queueOfNode.offer(tempNode.rightSon);
}
}
}
}
@Test
@DisplayName("이진트리 순회(넓이우선탐색: 레벨탐색)")
public void main() {
Node root = new Node(1);
root.leftSon = new Node(2);
root.rightSon = new Node(3);
root.leftSon.leftSon = new Node(4);
root.leftSon.rightSon = new Node(5);
root.rightSon.leftSon = new Node(6);
root.rightSon.rightSon = new Node(7);
Integer[] expectedAnswer1 = {1, 2, 3, 4, 5, 6, 7};
solution1(root);
assertArrayEquals(expectedAnswer1, answer.toArray());
}
}송아지 찾기(BFS: 상태트리탐색)
현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.
현수의 위치와 송아 지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.
송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.
최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.
- 입력설명
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다. - 출력설명
점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다. - 입력예제 1
5 14 - 출력예제 1
3 - 입력예제 2
8 3 - 출력예제 2
5
public class FindCalfBFS {
int[] directionWithLength = {1, -1, 5};
int[] checkArray = new int[10001];
Queue<Integer> queueOfPosition = new LinkedList<>();
public int solution1(int hyPosition, int calfPosition) {
checkArray[hyPosition] = 1;
queueOfPosition.offer(hyPosition);
int jump = 0;
while (!queueOfPosition.isEmpty()) {
for (int i = 0; i < queueOfPosition.size(); i++) {
int tempPosition = queueOfPosition.poll();
for (int j = 0; j < directionWithLength.length; j++) {
int nextPosition = tempPosition + directionWithLength[j];
if (nextPosition == calfPosition) {
return jump + 1;
} else if (nextPosition >= 1
&& nextPosition <= 10000
&& checkArray[nextPosition] == 0) {
checkArray[nextPosition] = 1;
queueOfPosition.offer(nextPosition);
}
}
}
jump++;
}
return jump;
}
@Test
@DisplayName("송아지 찾기(BFS: 상태트리탐색")
public void main() {
int expectedAnswer1 = 2;
int answer1 = solution1(5, 14);
assertEquals(expectedAnswer1, answer1);
int expectedAnswer2 = 1;
int answer2 = solution1(8, 3);
assertEquals(expectedAnswer2, answer2);
}
}Tree 말단 노드까지의 가장 짧은 경로
아래 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하세요.
각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를 길이로 하겠습니다.
가장 짧은 길이는 3번 노드까지의 길이인 1이다.
public class ShortestPathToTerminalNode {
private static class Node {
int data;
Node leftSon;
Node rightSon;
public Node(int data) {
this.data = data;
}
}
// DFS를 활용한 풀이
public int solution1(int level, Node root) {
if (Objects.isNull(root.leftSon) && Objects.isNull(root.rightSon)) {
return level;
} else {
return Math.min(solution1(level + 1, root.leftSon), solution1(level + 1, root.rightSon));
}
}
// BFS를 활용한 풀이
// 최단거리 문제는 BFS로 푸는 것이 정석
public int solution2(Node root) {
Queue<Node> queueOfNode = new LinkedList<>();
queueOfNode.offer(root);
int level = 0;
while (!queueOfNode.isEmpty()) {
for (int i = 0; i < queueOfNode.size(); i++) {
Node tempNode = queueOfNode.poll();
if (Objects.isNull(tempNode.leftSon)
&& Objects.isNull(tempNode.rightSon)) {
return level;
}
if (Objects.nonNull(tempNode.leftSon)) {
solution2(tempNode.leftSon);
}
if (Objects.nonNull(tempNode.rightSon)) {
solution2(tempNode.rightSon);
}
}
level++;
}
return level;
}
@Test
@DisplayName("Tree 말단 노드까지의 가장 짧은 경로")
public void main() {
Node root = new Node(1);
root.leftSon = new Node(2);
root.rightSon = new Node(3);
root.leftSon.leftSon = new Node(4);
root.leftSon.rightSon = new Node(5);
int expectedAnswer = 1;
int answer1 = solution1(0, root);
assertEquals(expectedAnswer, answer1);
int answer2 = solution2(root);
assertEquals(expectedAnswer, answer2);
}
}'Algorithm' 카테고리의 다른 글
| [Algorithm] Graph (0) | 2022.02.28 |
|---|---|
| [Algorithm] DFS 원리 (0) | 2022.02.28 |
| [Algorithm] Recursive (0) | 2022.02.27 |
| [Algorithm] Search (0) | 2022.02.25 |
| [Algorithm] Sorting (0) | 2022.02.25 |
