programmers | 블록 옮기기

코딩테스트 연습 - 블록 옮기기 | 프로그래머스

// https://school.programmers.co.kr/learn/courses/30/lessons/60063
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

// map<set<vector<int>>, int>  visited;
set<set<vector<int>>>  visited;
int                         max_len;
vector<int>                 goal;
int                         answer = INT_MAX;

bool ft_arrived_goal(set<set<vector<int>>> positions, int second) {
    set<set<vector<int>>>::iterator it;

    for (it = positions.begin(); it != positions.end(); it++) {
        if ((*it).find(goal) != (*it).end()) {
            return (true);
        }
    }
    return (false);
}

void ft_candidate(vector<vector<int>> board, set<set<vector<int>>>& positions, set<set<vector<int>>>& next_positions) {
    set<set<vector<int>>> rtn;

    vector<int> bigger;
    vector<int> smaller;
    
    set<set<vector<int>>>::iterator it;

    for (it = positions.begin(); it != positions.end(); ++it) {// which is bigger?
        if (*((*it).begin()) > *((*it).rbegin())) {
            bigger = *((*it).begin());
            smaller = *((*it).rbegin());
        } else {
            bigger = *((*it).rbegin());
            smaller = *((*it).begin());
        }

        bool horizontal;
        // is vertical? or horizontal?
        if (bigger[0] - smaller[0] == 0) { // y-axis same -> horizontal
            horizontal = true;
        } else if (bigger[1] - smaller[1] == 0) { // x-axis same -> vertical
            horizontal = false;
        }

        //can rotate?
        if (horizontal == true) {
            if ((smaller[0] != 0) && board[smaller[0] - 1][smaller[1]] == 0 && board[bigger[0] - 1][bigger[1]] == 0) {// up
                set<vector<int>> temp_set;
                vector<int> temp_vec = {smaller[0] - 1, smaller[1]};
                temp_set.insert(smaller);
                temp_set.insert(temp_vec);
                if (visited.find(temp_set) == visited.end())
                {
                    next_positions.insert(temp_set);
                    visited.insert(temp_set);
                }
            
                set<vector<int>> temp_set2;
                vector<int> temp_vec2 = {bigger[0] - 1, bigger[1]};
                temp_set2.insert(bigger);
                temp_set2.insert(temp_vec2);
                if (visited.find(temp_set2) == visited.end())
                {
                    next_positions.insert(temp_set2);
                    visited.insert(temp_set2);
                }
            }
            if ((smaller[0] != max_len) && board[smaller[0] + 1][smaller[1]] == 0 && board[bigger[0] + 1][bigger[1]] == 0) {// down
                set<vector<int>> temp_set;
                vector<int> temp_vec = {smaller[0] + 1, smaller[1]};
                temp_set.insert(smaller);
                temp_set.insert(temp_vec);
                if (visited.find(temp_set) == visited.end())
                {
                    next_positions.insert(temp_set);
                    visited.insert(temp_set);
                }
            
                set<vector<int>> temp_set2;
                vector<int> temp_vec2 = {bigger[0] + 1, bigger[1]};
                temp_set2.insert(bigger);
                temp_set2.insert(temp_vec2);
                if (visited.find(temp_set2) == visited.end())
                {
                    next_positions.insert(temp_set2);
                    visited.insert(temp_set2);
                }
            }
        } else { // vertical
            if ((smaller[1] != 0) && board[smaller[0]][smaller[1] - 1] == 0 && board[bigger[0]][bigger[1] - 1] == 0) {// left
                set<vector<int>> temp_set;
                vector<int> temp_vec = {smaller[0], smaller[1] - 1};
                temp_set.insert(smaller);
                temp_set.insert(temp_vec);
                if (visited.find(temp_set) == visited.end())
                {
                    next_positions.insert(temp_set);
                    visited.insert(temp_set);
                }
            
                set<vector<int>> temp_set2;
                vector<int> temp_vec2 = {bigger[0], bigger[1] - 1};
                temp_set2.insert(bigger);
                temp_set2.insert(temp_vec2);
                if (visited.find(temp_set2) == visited.end())
                {
                    next_positions.insert(temp_set2);
                    visited.insert(temp_set2);
                }
            }
            if ((smaller[1] != max_len) && board[smaller[0]][smaller[1] + 1] == 0 && board[bigger[0]][bigger[1] + 1] == 0) {// right
                set<vector<int>> temp_set;
                vector<int> temp_vec = {smaller[0], smaller[1] + 1};
                temp_set.insert(smaller);
                temp_set.insert(temp_vec);
                if (visited.find(temp_set) == visited.end())
                {
                    next_positions.insert(temp_set);
                    visited.insert(temp_set);
                }
            
                set<vector<int>> temp_set2;
                vector<int> temp_vec2 = {bigger[0], bigger[1] + 1};
                temp_set2.insert(bigger);
                temp_set2.insert(temp_vec2);
                if (visited.find(temp_set2) == visited.end())
                {
                    next_positions.insert(temp_set2);
                    visited.insert(temp_set2);
                }
            }
        }

        // can move?
        // down
        if (smaller[0] != max_len && bigger[0] != max_len && board[smaller[0] + 1][smaller[1]] == 0 && board[bigger[0] + 1][bigger[1]] == 0) {// right
            set<vector<int>> temp_set;
            vector<int> temp_vec1 = {smaller[0] + 1, smaller[1]};
            vector<int> temp_vec2 = {bigger[0] + 1, bigger[1]};
            temp_set.insert(temp_vec1);
            temp_set.insert(temp_vec2);
            if (visited.find(temp_set) == visited.end())
            {
                next_positions.insert(temp_set);
                visited.insert(temp_set);
            }
        }
        // up
        if (smaller[0] != 0 && bigger[0] != 0 && board[smaller[0] - 1][smaller[1]] == 0 && board[bigger[0] - 1][bigger[1]] == 0) {// right
            set<vector<int>> temp_set;
            vector<int> temp_vec1 = {smaller[0] - 1, smaller[1]};
            vector<int> temp_vec2 = {bigger[0] - 1, bigger[1]};
            temp_set.insert(temp_vec1);
            temp_set.insert(temp_vec2);
            if (visited.find(temp_set) == visited.end())
            {
                next_positions.insert(temp_set);
                visited.insert(temp_set);
            }
        }
        // left
        if (smaller[1] != 0 && bigger[1] != 0 && board[smaller[0]][smaller[1] - 1] == 0 && board[bigger[0]][bigger[1] - 1] == 0) {// right
            set<vector<int>> temp_set;
            vector<int> temp_vec1 = {smaller[0], smaller[1] - 1};
            vector<int> temp_vec2 = {bigger[0], bigger[1] - 1};
            temp_set.insert(temp_vec1);
            temp_set.insert(temp_vec2);
            if (visited.find(temp_set) == visited.end())
            {
                next_positions.insert(temp_set);
                visited.insert(temp_set);
            }
        }
        // right
        if (smaller[1] != max_len && bigger[1] != max_len && board[smaller[0]][smaller[1] + 1 ] == 0 && board[bigger[0]][bigger[1] + 1] == 0) {// right
            set<vector<int>> temp_set;
            vector<int> temp_vec1 = {smaller[0], smaller[1] + 1};
            vector<int> temp_vec2 = {bigger[0], bigger[1] + 1};
            temp_set.insert(temp_vec1);
            temp_set.insert(temp_vec2);
            if (visited.find(temp_set) == visited.end())
            {
                next_positions.insert(temp_set);
                visited.insert(temp_set);
            }
        }

    }
}

void ft_bfs(vector<vector<int>> board, int second, set<set<vector<int>>>& positions) {
    
    // // 만약에 도착한 곳이 이미, 더 적은 시간으로 도착한 적이 있다면, 재귀 중지.
    if (ft_arrived_goal(positions, second)) {
        answer = second;
        return ;
    }

    // 이동할 수 있는 후보를 추림.
    set<set<vector<int>>> next_positions;
    
    ft_candidate(board, positions, next_positions);

    // // 후보군을 돌면서 재귀.
    // for (int i = 0; i < candidate.size(); i++) {
    //     ft_dfs(board, second + 1, candidate[i]);
    // }
    ft_bfs(board, second + 1, next_positions);

    // positions를 받아오면, 이제 다음칸에 이동할 수 있는 얘들을 추려야함.
    // 전역변수 visited가 바뀌어야함.
    // map이 아닌 set으로 바뀌어야함.
    // 가장 처음 위치는 set에 추가하고 1깊이로 호출
    // 1초에 이동가능한 다음 candidates들을 vector에서 가져와서 계산하고, 
    // 다음초로 넘기면서 vector를 
}

int solution(vector<vector<int>> board) {
    max_len = board.size() - 1;
    goal = {max_len, max_len};

    set<vector<int>> position;
    vector<int> one{0, 0};
    vector<int> two{0, 1};
    position.insert(one);
    position.insert(two);

    set<set<vector<int>>> positions;
    positions.insert(position);
    visited.insert(position);

    ft_bfs(board, 0, positions);
    return answer;
}

int main() {
    // 이중 벡터 초기화 https://www.techiedelight.com/ko/initialize-two-dimensional-vector-cpp/
    vector<vector<int>> board = {
        {0, 0, 0, 1, 1},
        {0, 0, 0, 1, 0},
        {0, 1, 0, 1, 1},
        {1, 1, 0, 0, 1},
        {0, 0, 0, 0, 0}
    };

    cout << solution(board) << endl;
}

• 처음에 dfs로 짯다가, 14, 15번 테스트 케이스에서 시간초과가 뜸
• 질문하기 들어가보니 bfs로 풀어야 된다고 함.
• bfs는 재귀가 아니고 queue를 활용한, iteration에 가까워 보였음.
• queue는 쓰지 않았고, set을 사용함... 아무래도 그래서 set 데이터를 2개 따로 들고다님.