463 words
2 minutes
[BOJ] 벌집
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
2s | 128MB | 1 ≤ a, b ≤ 1,000,000 | Implementation |
그냥 간단히 구현하면 되는데… 벌집을 그래프로 만드는게 조금 어렵달까??
정답 코드
#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;
}