[PCCP] Lv3: 길 찾기 게임(42892) 해설

문제

- 문제 링크: 길 찾기 게임

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

- nodeinfo의 길이 N

- 이진 트리 구축 과정에서 nodeinfo 정렬: O(NlogN)

- 노드 추가하는 과정에서 최악의 경우: O(N^2)

- 전위 순회와 후위 순회: O(NlogN)

- 최악의 경우: O(N^2)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 노드 정의
struct Node {
    int id, x, y;
    Node* left = nullptr;
    Node* right = nullptr;
    
    Node(int id, int x, int y) : id(id), x(x), y(y) {}
};

// 이진트리 정의
class BinaryTree {
private:
    Node* root = nullptr;
    
    // 노드 좌표를 기준으로 정렬할 때 기준이 되는 함수
    static bool compareNodes(Node* a, Node* b) {
        if (a->y != b-> y)
            return a->y > b->y;
        return a->x < b->x;
    }
    
    // 새 노드를 추가하는 함수
    Node *addNode(Node* current, Node* newNode) {
        if (current == nullptr)
            return newNode;
        //추가하려는 노드의 좌표를 기준으로 현재 노드의 좌, 우 여부 판단 후 추가
        if (newNode->x < current->x)
            current->left = addNode(current->left, newNode);
        else
            current->right = addNode(current->right, newNode);
        
        return current;
    }
    
    // 전위 순회를 진행하며 경로를 저장하는 함수
    void preOrder(Node* node, vector<int>& traversal) {
        if (node == nullptr)
            return;
        traversal.push_back(node->id);
        preOrder(node->left, traversal);
        preOrder(node->right, traversal);
    }
    
    // 후위 순회를 진행하며 경로를 저장하는 함수
    void postOrder(Node* node, vector<int>& traversal) {
        if (node == nullptr)
            return;
        postOrder(node->left, traversal);
        postOrder(node->right, traversal);
        traversal.push_back(node->id);
    }
    
public:
    BinaryTree() : root(nullptr) {}
    
    // nodeinfo를 기준으로 이진 트리를 구축하는 함수
    void buildTree(const vector<vector<int>>& nodeInfo) {
        vector<Node*> nodes;
        // 각 노드의 (인덱스, x좌표, y좌표) 정보를 nodes에 저장
        for (int i = 0; i < nodeInfo.size(); ++i) {
            nodes.push_back(new Node(i + 1, nodeInfo[i][0], nodeInfo[i][1]));
        }
        
        // 이진 트리를 구축하기 위해 노드를 정렬
        sort(nodes.begin(), nodes.end(), compareNodes);
        // 이진 트리 구축
        for (Node* node : nodes) {
            root = addNode(root, node);
        }
    }
    
    // 전위 순회 후 경로를 반환하는 함수
    vector<int> getPreOrderTraversal() {
        vector<int> traversal;
        preOrder(root, traversal);
        
        return traversal;
    }
    
    // 후위 순회 후 경로를 반환하는 함수
    vector<int> getPostOrderTraversal() {
        vector<int> traversal;
        postOrder(root, traversal);
        
        return traversal;
    }
};

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    BinaryTree tree;
    
    // 이진 트리를 구축하고 순회 결과를 반환
    tree.buildTree(nodeinfo);
    vector<int> preOrder = tree.getPreOrderTraversal();
    vector<int> postOrder = tree.getPostOrderTraversal();
    
    answer.push_back(preOrder);
    answer.push_back(postOrder);
    return answer;
}

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N은 노드의 길이

- makeBT()는 노드 번호를 배열을 생성하고 정렬하기 위해 O(NlogN)이 필요

- 이후 각 노드를 삽입할 때의 시간 복잡도는 O(N)이고 이를 N번 반복하므로 시간 복잡도는 O(N^2)

- 트리를 구축하여 각각 순회하는 동작은 노드를 한 번씩 방문하므로 O(N)

- 최종 시간 복잡도: O(N^2)

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {

    // Node 클래스 정의
    private static class Node {
        int x, y, num; // 노드의 좌표, 번호 저장
        Node left, right; // 노드의 왼쪽, 오른쪽 자식 노드

        public Node(int num, int x, int y) {
            this.num = num;
            this.x = x;
            this.y = y;
        }
    }

    // 이진 트리 생성 메소드
    private static Node makeBT(int[][] nodeinfo) {
        // 각 노드에 대한 좌표, 번호를 배열에 저장
        Node[] nodes = new Node[nodeinfo.length];
        for (int i = 0; i < nodeinfo.length; i++) {
            nodes[i] = new Node(i + 1, nodeinfo[i][0], nodeinfo[i][1]);
        }

        // y 기준으로 내림차순 정렬, y가 같다면 x를 기준으로 오름차순 정렬
        Arrays.sort(nodes, (o1, o2) -> {
            if (o1.y == o2.y)
                return Integer.compare(o1.x, o2.x);
            return Integer.compare(o2.y, o1.y);
        });

        Node root = nodes[0]; // 맨 처음 노드는 무조건 루트

        for (int i = 1; i < nodes.length; i++) {
            Node parent = root;
            while (true) {
                // 부모 노드의 x좌표가 더 크면 왼쪽으로
                if (nodes[i].x < parent.x) {
                    if (parent.left == null) {
                        parent.left = nodes[i];
                        break;
                    }
                    else {
                        parent = parent.left;
                    }
                }
                // 부모 노드의 x좌표가 더 작거나 같으면 오른쪽으로
                else {
                    if (parent.right == null) {
                        parent.right = nodes[i];
                        break;
                    }
                    else {
                        parent = parent.right;
                    }
                }
            }
        }

        return nodes[0];
    }

    // 전위 순회 메소드
    private static void preOrder(Node curr, ArrayList<Integer> answer) {
        if (curr == null) {
            return;
        }
        answer.add(curr.num);
        preOrder(curr.left, answer);
        preOrder(curr.right, answer);
    }

    // 후위 순회 메소드
    private static void postOrder(Node curr, ArrayList<Integer> answer) {
        if (curr == null) {
            return;
        }
        postOrder(curr.left, answer);
        postOrder(curr.right, answer);
        answer.add(curr.num);
    }

    public int[][] solution(int[][] nodeinfo) {
        Node root = makeBT(nodeinfo); // 이진트리 생성

        ArrayList<Integer> preOrderList = new ArrayList<>();
        preOrder(root, preOrderList); // 전위 순회
        ArrayList<Integer> postOrderList = new ArrayList<>();
        postOrder(root, postOrderList); // 후위 순회

        // 결과 반환
        int[][] answer = new int[2][nodeinfo.length];
        answer[0] = preOrderList.stream().mapToInt(Integer::intValue).toArray();
        answer[1] = postOrderList.stream().mapToInt(Integer::intValue).toArray();

        return answer;
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 노드의 길이

- make_BT()는 노드 번호 리스트를 생성하고 정렬: O(NlogN)

- 각 노드 삽입의 시간 복잡도는 O(N)이고 이를 N번 반복하는데 걸리는 시간 복잡도: O(N^2)

- 트리를 구축하여 각각 순회하는 동작은 노드를 한 번씩 방문: O(N)

- 최종 시간 복잡도: O(N^2)

from collections import deque

# Node 클래스 정의
class Node:
    def __init__(self, info, num, left=None, right=None):
        self.info = info # 노드의 좌표 정보 저장
        self.left = left # 노드의 왼쪽 자식 노드
        self.right = right # 노드의 오른쪽 자식 노드
        self.num = num # 노드의 번호
        
    # 왼쪽 자식 노드가 있는지 확인하는 함수
    def has_left(self):
        return self.left is not None
    
    # 오른쪽 자식노드가 있는지 확인하는 함수
    def has_right(self):
        return self.right is not None
    
# 이진 트리 생성 함수
def make_BT(nodeinfo):
    nodes = [i for i in range(1, len(nodeinfo) + 1)]  # 노드의 번호 리스트 생성
    nodes.sort(key=lambda x: (nodeinfo[x - 1][1], -nodeinfo[x - 1][0]), reverse=True)
    root = None
    for i in range(len(nodes)):
        if root is None:
            root = Node(nodeinfo[nodes[0] - 1], nodes[0])
        else:
            parent = root
            node = Node(nodeinfo[nodes[i] - 1], nodes[i])
            while True:
             # 부모 노드의 x좌표가 더 크면 왼쪽으로
                if node.info[0] < parent.info[0]:
                    if parent.has_left():
                        parent = parent.left
                        continue
                    parent.left = node
                    break
            # 부모 노드의 x좌표가 더 작거나 같으면 오른쪽으로
                else:
                    if parent.has_right():
                        parent = parent.right
                        continue
                    parent.right = node
                    break
    return root

# 전위 순회 함수
def pre_order(root, answer):
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        answer[0].append(node.num)
        stack.append(node.right)
        stack.append(node.left)

# 후위 순회 함수
def post_order(root, answer):
    stack = [(root, False)]
    while stack:
        node, visited = stack.pop()
        if node is None:
            continue
        if visited:
            answer[1].append(node.num)
        else:
            stack.append((node, True))
            stack.append((node.right, False))
            stack.append((node.left, False))

# 주어진 좌표 정보를 이용하여 이진 트리를 생성하고, 전위 순회와 후위 순회한 결과를 반환하는 함수
def solution(nodeinfo):
    answer = [[], []] # 결과를 저장할 리스트 초기화
    root = make_BT(nodeinfo) # 이진 트리 생성
    pre_order(root, answer) # 전위 순회
    post_order(root, answer) # 후위 순회
    return answer # 결과 반환

solution 2) 재귀를 이용한 풀이

- 재귀의 최대 깊이 설정 필요

import sys
sys.setrecursionlimit(10**6)

from collections import deque

# Node 클래스 정의
class Node:
    def __init__(self, info, num, left=None, right=None):
        self.info = info # 노드의 좌표 정보 저장
        self.left = left # 노드의 왼쪽 자식 노드
        self.right = right # 노드의 오른쪽 자식 노드
        self.num = num # 노드의 번호
        
    # 왼쪽 자식 노드가 있는지 확인하는 함수
    def has_left(self):
        return self.left is not None
    
    # 오른쪽 자식노드가 있는지 확인하는 함수
    def has_right(self):
        return self.right is not None
    
# 이진 트리 생성 함수
def make_BT(nodeinfo):
    nodes = [i for i in range(1, len(nodeinfo) + 1)]  # 노드의 번호 리스트 생성
    nodes.sort(key=lambda x: (nodeinfo[x - 1][1], -nodeinfo[x - 1][0]), reverse=True)
    root = None
    for i in range(len(nodes)):
        if root is None:
            root = Node(nodeinfo[nodes[0] - 1], nodes[0])
        else:
            parent = root
            node = Node(nodeinfo[nodes[i] - 1], nodes[i])
            while True:
             # 부모 노드의 x좌표가 더 크면 왼쪽으로
                if node.info[0] < parent.info[0]:
                    if parent.has_left():
                        parent = parent.left
                        continue
                    parent.left = node
                    break
            # 부모 노드의 x좌표가 더 작거나 같으면 오른쪽으로
                else:
                    if parent.has_right():
                        parent = parent.right
                        continue
                    parent.right = node
                    break
    return root

# 전위 순회 함수(재귀)
def pre_order(root, answer):
    if root is None:
        return
    answer[0].append(root.num)
    pre_order(root.left, answer)
    pre_order(root.right, answer)
    
# 후위 순회 함수(재귀)
def post_order(root, answer):
    if root is None:
        return
    post_order(root.left, answer)
    post_order(root.right, answer)
    answer[1].append(root.num)

# 주어진 좌표 정보를 이용하여 이진 트리를 생성하고, 전위 순회와 후위 순회한 결과를 반환하는 함수
def solution(nodeinfo):
    answer = [[], []] # 결과를 저장할 리스트 초기화
    root = make_BT(nodeinfo) # 이진 트리 생성
    pre_order(root, answer) # 전위 순회
    post_order(root, answer) # 후위 순회
    return answer # 결과 반환

solution 3)

import

 

(JavaScript)

solution 1)

- N: 노드의 길이

- makeBT()는 노드 번호 배열을 생성하고 정렬: O(NlogN)

- 각 노드를 삽입에 O(N)이 걸리고 이를 N번 반복: O(N^2)

- 트리 구축하여 각각 순회하는 동작은 노드를 한 번씩 방문: O(N)

- 최종 시간 복잡도: O(N^2)

// Node 클래스 정의
class Node {
    constructor(info, num, left = null, right = null) {
        this.info = info; // 노드의 좌표 정보 저장
        this.left = left; // 노드의 왼쪽 자식 노드
        this.right = right; // 노드의 오른쪽 자식 노드
        this.num = num; // 노드의 번호
    }
    
    // 왼쪽 자식 노드가 있는지 확인하는 함수
    hasLeft() {
        return this.left !== null;
    }
    
    // 오른쪽 자식 노드가 있는지 확인하는 함수
    hasRight() {
        return this.right !== null;
    }
}

// 이진 트리 생성 함수
function makeBT(nodeinfo) {
    // 노드의 번호 배열 생성
    const nodes = Array.from({length: nodeinfo.length}, (_, i) => i + 1);
    nodes.sort((a, b) => {
        const [ax, ay] = nodeinfo[a-1];
        const [bx, by] = nodeinfo[b-1];
        return ay === by ? ax - bx : by - ay;
    });
    
    let root = null;
    for (const node of nodes) {
        if (!root) {
            root = new Node(nodeinfo[node - 1], node);
        } else {
            let parent = root;
            const newNode = new Node(nodeinfo[node - 1], node);
            while (true) {
                // 부모 노드의 x좌표가 더 크면 왼쪽으로
                if (newNode.info[0] < parent.info[0]) {
                    if (parent.hasLeft()) {
                        parent = parent.left;
                        continue;
                    }
                    parent.left = newNode;
                    break;
                } else {
                    // 부모 노드의 x좌표가 더 작거나 같으면 오른쪽으로
                    if (parent.hasRight()) {
                        parent = parent.right;
                        continue;
                    } 
                    parent.right = newNode;
                    break;
                }
            }
        }
    }
    return root;
}

// 전위 순회 함수
function preOrder(root, answer) {
    const stack = [root];
    while (stack.length) {
        const node = stack.pop();
        if (!node) {
            continue;
        }
        answer[0].push(node.num);
        stack.push(node.right);
        stack.push(node.left);
    }
}

// 후위 순회 함수
function postOrder(root, answer) {
    const stack = [[root, false]];
    while (stack.length) {
        const [node, visited] = stack.pop();
        if (!node) {
            continue;
        }
        if (visited) {
            answer[1].push(node.num);
        } else {
            stack.push([node, true]);
            stack.push([node.right, false]);
            stack.push([node.left, false]);
        }
    }
}

// 주어진 좌표 정보를 이용하여 이진 트리를 생성하고, 전위 순회와 후위 순회한 결과를 반환하는 함수
function solution(nodeinfo) {
    const answer = [[], []]; // 결과를 저장할 배열 초기화
    const root = makeBT(nodeinfo); // 이진 트리 생성
    preOrder(root, answer); // 전위 순회
    postOrder(root, answer); // 후위 순회
    return answer; // 결과 반환
}

solution 2) 재귀를 활용한 풀이

// Node 클래스 정의
class Node {
    constructor(info, num, left = null, right = null) {
        this.info = info; // 노드의 좌표 정보 저장
        this.left = left; // 노드의 왼쪽 자식 노드
        this.right = right; // 노드의 오른쪽 자식 노드
        this.num = num; // 노드의 번호
    }
    
    // 왼쪽 자식 노드가 있는지 확인하는 함수
    hasLeft() {
        return this.left !== null;
    }
    
    // 오른쪽 자식 노드가 있는지 확인하는 함수
    hasRight() {
        return this.right !== null;
    }
}

// 이진 트리 생성 함수
function makeBT(nodeinfo) {
    // 노드의 번호 배열 생성
    const nodes = Array.from({length: nodeinfo.length}, (_, i) => i + 1);
    nodes.sort((a, b) => {
        const [ax, ay] = nodeinfo[a-1];
        const [bx, by] = nodeinfo[b-1];
        return ay === by ? ax - bx : by - ay;
    });
    
    let root = null;
    for (const node of nodes) {
        if (!root) {
            root = new Node(nodeinfo[node - 1], node);
        } else {
            let parent = root;
            const newNode = new Node(nodeinfo[node - 1], node);
            while (true) {
                // 부모 노드의 x좌표가 더 크면 왼쪽으로
                if (newNode.info[0] < parent.info[0]) {
                    if (parent.hasLeft()) {
                        parent = parent.left;
                        continue;
                    }
                    parent.left = newNode;
                    break;
                } else {
                    // 부모 노드의 x좌표가 더 작거나 같으면 오른쪽으로
                    if (parent.hasRight()) {
                        parent = parent.right;
                        continue;
                    } 
                    parent.right = newNode;
                    break;
                }
            }
        }
    }
    return root;
}

// 전위 순회 함수(재귀)
function preOrder(root, answer) {
    if (root === null)
        return;
    
    answer[0].push(root.num);
    preOrder(root.left, answer);
    preOrder(root.right, answer);
}

// 후위 순회 함수(재귀)
function postOrder(root, answer) {
    if (root === null)
        return;
    
    postOrder(root.left, answer);
    postOrder(root.right, answer);
    answer[1].push(root.num);
}

// 주어진 좌표 정보를 이용하여 이진 트리를 생성하고, 전위 순회와 후위 순회한 결과를 반환하는 함수
function solution(nodeinfo) {
    const answer = [[], []]; // 결과를 저장할 배열 초기화
    const root = makeBT(nodeinfo); // 이진 트리 생성
    preOrder(root, answer); // 전위 순회
    postOrder(root, answer); // 후위 순회
    return answer; // 결과 반환
}

solution 3)

import