Compy's Blog
463 words
2 minutes
[BOJ] 벌집
2025-09-29

벌집

TimeLimitMemoryLimitConditionTAG
2s128MB1 ≤ a, b ≤ 1,000,000Implementation

그냥 간단히 구현하면 되는데… 벌집을 그래프로 만드는게 조금 어렵달까??

정답 코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <climits>
using namespace std;
using ll = long long;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

vector<int> board[1'500'000];
pair<int, int> visited[1'500'000];


void connect(int a, int b){
    board[a].push_back(b);
    board[b].push_back(a);
}

void makeBoard(){
    // 1,000,000
    // 3n(n+1)이네
    int current = 1;
    int cycle = 0;
    for(int n = 1; current <= 1'000'001; n++){
        int pre = 3 * (n - 1) * n + 1;
        int end = 3 * n * (n+1) + 1;
        
        
//        connect(pre, end);
        
//        cout << current << "\n";
//        
//        cout << "term: " << pre<< " " << end <<" " << 3 * (n - 2) * (n - 1) + 2<< "\n\n";
        connect(current, current - 1);
        connect(current+1, end);
        if(3 * (n - 2) * (n-1) + 1 > 0){
            connect(current, 3 * (n - 2) * (n-1) + 1);
            connect(current+1, 3 * (n - 2) * (n-1) + 1+1);
        }
        
        
        int term = 1;
        for(current ++; current < end; current++){
            connect(current, current-1);
//            cout << current << "\n";
//            
//            cout << "term: " << term<< " " << pre << "\n\n";
            if(term > cycle){
                connect(current, pre);
                term = 1;
//                cout << current << "\n";
                
            }else{
                connect(current, pre++);
                connect(current, pre);
                term++;
            }
            
            
            if(pre > 3 * (n - 1) * n + 1) pre = 3 * (n - 2) * (n-1) + 2;
        }
        
        
        
        cycle ++;
        
    }
    
    
    board[1].clear();
    for(int i = 2; i < 8; i++) board[1].push_back(i);
    
//    connect(8,  2); 여기 라인 대각선이 문제임
//    connect(19, 7);
}



vector<int> solution(int start, int finish){
    
    
    queue<int> q;
    
    for(int i = 1; i <= 1'000'001; i++){
        visited[i] = {1000000000, -1}; // cost, path
    }
    
//    cout << "check!";
    
    q.push(start);
    visited[start] = {0, -1};
    
    
    while(!q.empty()){
        int current = q.front(); q.pop();
        
        for(int next : board[current]){
            if(next >= 1'000'100) continue;
            if(visited[next].first <= visited[current].first + 1) continue;
            
            visited[next].first = visited[current].first + 1;
            visited[next].second = current;
            
            q.push(next);
        }
    }
    
    
    vector<int> result;
    int current = finish;
    while(visited[current].second != -1){
        result.push_back(current);
        current = visited[current].second;
    }
    result.push_back(start);
    
    reverse(result.begin(), result.end());
    return result;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    

    
    makeBoard();
    
    int a, b;
    cin >> a >> b;
    
//    for(int i : board[1]){
//        cout << i << " ";
//    }
    vector<int> result;
    result = solution(a, b);
    
    for(int i : result) cout << i << " ";
    
    
    return 0;
}
[BOJ] 벌집
https://compy07.github.io/Blog/posts/boj/1385/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-09-29