[백준] 1463번

이 문제는 visited 여부도 고려했어야 했다.
이 부분을 고려 안해서 시간초과가 굉장히 많이 생겼다.

#include <map>
#include <iostream>

typedef struct node{
    int data;
    int depth;
}node;


int main() {
    int x, index = 0, count = 1;
    std::cin >> x;
    std::map<int, node> root;
    std::map<int, bool>visited;

    root[0].data = x;
    root[0].depth = 0;
    visited[root[0].data] = false;
    while (root[index].data > 1) {
        if (visited[root[index].data]) {
            index++;
            continue;
        }
        if (root[index].data % 3 == 0) {
            root[count].data = root[index].data / 3;
            root[count++].depth = root[index].depth + 1;
        }
        if (root[index].data % 2 == 0) {
            root[count].data = root[index].data / 2;
            root[count++].depth = root[index].depth + 1;
        }
        root[count].data = root[index].data - 1;
        root[count++].depth = root[index].depth + 1;
        visited[root[index++].data] = true;
    }
    std::cout << root[index].depth << std::endl;


    return 0;
}

이건 depth limit dfs로 풀었지만, 메모리 초과로 인해 실패한 녀석

역시 bfs로 풀어야 할 듯하다.

    #include <iostream>

    typedef struct node {
        int data;
        node *parent;
        node *three;
        node *two;
        node *one;
        int depth;
    }node;

    bool dlDFS(node* root, int depth) {
        // std::cout <<"node->parent : " << root->parent->data << std::endl;
        // std::cout <<"node->data : " <<root->data << std::endl;
        // std::cout <<"depth : " << root->depth << std::endl;
        if (root->data == 1) {
            return true;
        }
        if (root->depth > depth) {
            return false;
        }
        if (root->three == nullptr && root->two == nullptr && root->one == nullptr) {
            if (root->data % 3 == 0) {
                node* temp = new node();
                temp->data = root->data/3;
                temp->parent = root;
                temp->three = nullptr;
                temp->two = nullptr;
                temp->one = nullptr;
                temp->depth = root->depth + 1;
                root->three = temp;
            }
            if (root->data % 2 == 0) {
                node* temp = new node();
                temp->data = root->data/2;
                temp->parent = root;
                temp->three = nullptr;
                temp->two = nullptr;
                temp->one = nullptr;
                temp->depth = root->depth + 1;
                root->two = temp;
            }
            node* temp = new node();
            temp->data = root->data-1;
            temp->parent = root;
            temp->three = nullptr;
            temp->two = nullptr;
            temp->one = nullptr;
            temp->depth = root->depth + 1;
            root->one = temp;
            return false;
        } else {
            bool temp[3] = {false, false, false};
            if (root->three != nullptr) {
                temp[2] = dlDFS(root->three, depth);
            }
            if (root->two != nullptr) {
                temp[1]  = dlDFS(root->two, depth);
            }
            if (root->one != nullptr) {
                temp[0]  = dlDFS(root->one, depth);
            }
            // std::cout << temp[0] << " " <<temp[1] << " " << temp[2] << std::endl;
            // std::cout << "**********************************" << std::endl;
            return temp[2] || temp[1] || temp[0];
        }
    }

    int main() {
        int x;
        std::cin >> x;
        node *head = new node();
        head->data = x;
        head->parent = head;
        head->depth = 0;
        head->three = nullptr;
        head->two = nullptr;
        head->one = nullptr;
        int depth = 0;
        while (true) {
            // std::cout << "real depth : "<<depth << std::endl;
            if (dlDFS(head, depth)) {
                break;
            }
            depth++;
            // std::cout << "================================" << std::endl;
        }

        std::cout << depth << std::endl;
        return 0;
    }