BST 구현하기
프로그래머스 2019 KAKAO BLIND RECRUITMENT Level 3 문제 길 찾기 게임을 Java를 이용하여 풀어보았다. 이진 탐색 트리를 주어진 조건에 맞춰 직접 구현해야 하는 문제였다. 푸는 데 꽤나 오래 걸렸다...
문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/42892
주어진 조건에 맞게 BST 구현하기
보통은 추가할 노드와 그 노드의 자식 노드들의 정보들을 주면 그에 따라 이진 탐색 트리를 만들면 되지만 여기서는 (x,y) 좌푯값을 주고 그에 따라 트리에서의 위치를 찾을 수 있는 로직을 만들어 부모 노드와 자식 노드들을 연결해서 구현해야 했다. 
문제에서 주어진 대로 (x,y) 위치에 따라 노드들간의 연결 관계가 결정된다. 따라서 x 좌푯값과 y 좌푯값에 따라 적절히 위치시켜주는 것이 핵심이었다.
y 좌푯값 내림차순으로 리스트 만들기
트리의 가장 위에서부터 아래로 내려오며 노드들을 추가해준다고 하면 가장 높은 level에 있는 노드들부터 가장 아래에 있는 노드들까지 정렬해줄 필요가 있었다.
이를 위해서 주어진 모든 노드 정보들의 y값만 중복 없이 따로 추가해준 후에 내림차순으로 정렬해주었다.
이를 코드로 표현하면 다음과 같다.
static ArrayList<Integer> yList = new ArrayList<>();
for (int i = 0; i < nodeinfo.length; i++) {
if (yList.indexOf(nodeinfo[i][1]) < 0) yList.add(nodeinfo[i][1]); // 중복 없이 추가가 가능하다
}
Collections.sort(yList, Collections.reverseOrder());여기서 중복 없이 y값들을 추가해주고 거기에 추가로 정렬까지 해야했기 때문에 Set을 쓰지 않고 ArrayList를 쓰되, 값을 추가해줄 때 indexOf(Object o) 를 사용했다.
만약 indexOf(Object o)의 값이 -1로 나오면 리스트에 존재하지 않는 값이라는 의미이기 때문에 이걸 활용해서 y값들을 추가해줬다.
x 좌푯값 오름차순으로 노드 정보 정렬하기
위에서부터 아래로 내려오며 노드들을 추가해준다면, 그 다음으로 고려할 것은 같은 x값들을 가진 수평선 상에 있는 노드들을 추가해주는 것이다.
이때 처음에는 저장해둔 모든 노드 정보들을 x값 오름차순으로 정렬해줘야 제자리를 잘 찾아갈 거라 생각해서 모든 노드 정보들을 x 좌푯값 오름차순으로 정렬한 후에 노드 추가 작업을 해줬다.
근데 이 글을 작성하며 생각해보니 x 좌푯값대로는 정렬해줄 필요없이, 노드 추가 작업을 해주는 tree.search() 메소드에서 알아서 x 좌푯값을 비교해서 추가를 해주니 굳이 한 번 더 하는 게 아닐까? 하는 생각에 노드 정보 x 좌표 오름차순 정렬 코드를 지우고 수행해봤다. 그랬더니 된다!
이미 노드 추가 작업을 하는 search() 메소드에서 비교를 해주니 중복된 작업이었던 듯하다.
BST 구현하기
그렇다면 이제 트리 구현 코드를 한 번 살펴보자.
트리를 채워줄 노드 클래스와 트리 클래스 두 가지를 보자.
Node
Node 클래스는 각 노드의 정보인 data와 (x,y) 정보와 Node left 와 Node right 로 이루어져있다.
static class Node {
int data;
int x;
int y;
Node left;
Node right;
Node(int data, int x, int y) {
this.data = data;
this.x = x;
this.y = y;
}
}생성자로는 자식 노드들은 넘겨줄 필요 없다. add() 에서 직접 left와 right를 찾아줄 것이기 때문이다.
Tree
Tree 클래스의 클래스 변수로는
Node root// 루트 노드ArrayList<Integer> preorder// 전위 순회 결과 담아줄 변수ArrayList<Integer> postorder// 후위 순회 결과 담아줄 변수
가 있다.
메소드로는 (노드 추가, 노드 들어갈 위치 찾기, 전위 순회 결과 생성, 후위 순회 결과 생성) 이렇게 네 개가 있다.
코드로 확인해보자.
class Tree {
Node root;
ArrayList<Integer> preorder = new ArrayList<>(), postorder = new ArrayList<>();
void add(int data, int x, int y) {
if (root == null) { // 루트가 아직 비어있으면
root = new Node(data, x, y);
root.left = null;
root.right = null;
} else search(null, root, data, x, y); // 들어갈 자리를 찾아주자
}
void search(Node parent, Node curNode, int data, int x, int y) {
if (curNode == null) { // 빈 자리 찾았으면 드가자
if (parent.x > x) parent.left = new Node(data, x, y); // 부모 x값보다 작으면 왼쪽에 들어가자
if (parent.x < x) parent.right = new Node(data, x, y); // 부모 x값보다 크면 오른쪽에 들어가자
} else {
if (curNode.x > x) search(curNode, curNode.left, data, x, y); // 현재 노드보다 x값 작으면 왼쪽 검색
if (curNode.x < x) search(curNode, curNode.right, data, x, y); // 현재 노드보다 x값 크면 오른쪽 검색
}
}
void createPreorder(Node cur) { // root -> left -> right
preorder.add(cur.data);
if (cur.left != null) createPreorder(cur.left);
if (cur.right != null) createPreorder(cur.right);
}
void createPostorder(Node cur) { // left -> right -> root
if (cur.left != null) createPostorder(cur.left);
if (cur.right != null) createPostorder(cur.right);
postorder.add(cur.data);
}
}노드 정보 받고 트리 생성하기
모든 준비가 끝났다. 입력값으로 주어지는 노드 정보들을 노드 list 에 저장하고 트리를 생성해주자.
int[][] solution(int[][] nodeinfo) {
int[][] answer = new int[2][];
Tree tree = new Tree();
for (int i = 0; i < nodeinfo.length; i++) {
nodeList.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1])); // 노드 정보 받아주자
if (yList.indexOf(nodeinfo[i][1]) < 0) yList.add(nodeinfo[i][1]); // y값만 중복없이 추가하자
}
Collections.sort(yList, Collections.reverseOrder()); // y값 내림차순 정렬하자
for (int y : yList) { // 위에서부터 내려오며
int curY = y;
for (Node node : nodeList) // 수평선으로 움직이며
if (node.y == curY) tree.add(node.data, node.x, node.y); // 같은 높이에 있는 노드들 추가하자
}
tree.createPreorder(tree.root);
tree.createPostorder(tree.root);
answer[0] = tree.preorder.stream().mapToInt(Integer::intValue).toArray(); // int[] 로 바꿔주자
answer[1] = tree.postorder.stream().mapToInt(Integer::intValue).toArray();
return answer;
}이제 위에서 작성한 코드를 모두 합치면 다음과 같다. 내가 제출한 코드다.
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
public class PathFinding {
static ArrayList<Node> nodeList = new ArrayList<>();
static ArrayList<Integer> yList = new ArrayList<>();
static int[][] solution(int[][] nodeinfo) {
int[][] answer = new int[2][];
Tree tree = new Tree();
for (int i = 0; i < nodeinfo.length; i++) {
nodeList.add(new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]));
if (yList.indexOf(nodeinfo[i][1]) < 0) yList.add(nodeinfo[i][1]);
}
Collections.sort(yList, Collections.reverseOrder());
for (int y : yList) {
int curY = y;
for (Node node : nodeList)
if (node.y == curY) tree.add(node.data, node.x, node.y);
}
tree.createPreorder(tree.root);
tree.createPostorder(tree.root);
answer[0] = tree.preorder.stream().mapToInt(Integer::intValue).toArray();
answer[1] = tree.postorder.stream().mapToInt(Integer::intValue).toArray();
return answer;
}
public static void main(String args[]) throws IOException {
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
int[][] nodeInfo = {{5, 3}, {11, 5}, {13, 3}, {3, 5}, {6, 1}, {1, 3}, {8, 6}, {7, 2}, {2, 2}};
int[][] result = solution(nodeInfo);
for (int data : result[0]) bfw.write(data + " ");
bfw.newLine();
for (int data : result[1]) bfw.write(data + " ");
bfw.close();
}
static class Node {
int data;
int x;
int y;
Node left;
Node right;
Node(int data, int x, int y) {
this.data = data;
this.x = x;
this.y = y;
}
}
static class Tree {
Node root;
ArrayList<Integer> preorder = new ArrayList<>(), postorder = new ArrayList<>();
void add(int data, int x, int y) {
if (root == null) { // 루트가 아직 비어있으면
root = new Node(data, x, y);
root.left = null;
root.right = null;
} else search(null, root, data, x, y); // 들어갈 자리를 찾아주자
}
void search(Node parent, Node curNode, int data, int x, int y) {
if (curNode == null) { //
if (parent.x > x) parent.left = new Node(data, x, y);
if (parent.x < x) parent.right = new Node(data, x, y);
} else {
if (curNode.x > x) search(curNode, curNode.left, data, x, y);
if (curNode.x < x) search(curNode, curNode.right, data, x, y);
}
}
void createPreorder(Node cur) { // root -> left -> right
preorder.add(cur.data);
if (cur.left != null) createPreorder(cur.left);
if (cur.right != null) createPreorder(cur.right);
}
void createPostorder(Node cur) { // left -> right -> root
if (cur.left != null) createPostorder(cur.left);
if (cur.right != null) createPostorder(cur.right);
postorder.add(cur.data);
}
}
}이 문제를 마주했을 때 BST를 직접 구현해서 써본 적이 없어서 먼저 백준 1991번을 먼저 풀고 이 문제를 풀어봤다. 혹시 BST가 익숙하지 않다면 위 문제를 먼저 풀어보고 이 문제로 오면 도전해볼 만하다.
오늘 배운 것
- BST 구현 잘 기억해두자
- 자료구조 지식이
존나부족하다 흙
