[SWEA] 4112번 이상한 피라미드 탐험

4112번 이상한 피라미드 탐험

문제 링크

 

해결방법

BFS 탐색을 통해 최단거리를 구하는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

그래프의 구조가 복잡하지만, 1차원 배열을 통해 O(10,000) 시간동안 완전탐색을 수행할 수 있다

BFS 를 수행하기 위해 노드의 간선을 연결해야한다

 

직접 관계를 그려보면, 아래와 같은 간선의 결과를 얻을 수 있다

1 - 2, 3
------------------------------
2 - [1], 3, 4, 5
3 - [1], [2], 5, 6
------------------------------
4 - [2], 5, 7, 8
5 - [2], [3], [4], 6, 8, 9
6 - [3], [5], 9, 10
------------------------------
7 - [4], 8, 11, 12
8 - [4], [5], [7], 9, 12, 13
9 - [5], [6], [8], 10, 3, 14
10 - [6], [9], 14, 15

이제 규칙을 찾을 수 있다

이전 노드는 이미 간선 연결을 했다는 가정하에, 마지막 인덱스를 제외하고는 3개의 노드와 새롭게 연결된다. 마지막 인덱스는 2개의 노드와 새로 연결된다.

이제 이런 규칙을 이용해서 간선을 연결하고, 완전탐색을 수행하면 된다!!

 

 

소스코드

문제 해결 시간 : 1h

메모리 : 13460 KB

시간 : 787 ms

#include <iostream>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#define MAX 10001
using namespace std;

int testcase;
int a,b;
int dist[MAX];
bool visited[MAX];
vector<vector<int>> adj(MAX);

void setAdj(){
    int ind = 1;
    
    for(int i=1; i<=1000; i++){
        for(int j=1; j<=i; j++){
            if(j==i){
                if(ind+i < MAX){
                    adj[ind].push_back(ind+i);
                    adj[ind+i].push_back(ind);
                }
                
                if(ind+i+1 < MAX){
                    adj[ind].push_back(ind+i+1);
                    adj[ind+i+1].push_back(ind);
                }
            }else{
                if(ind+1 < MAX){
                    adj[ind].push_back(ind+1);
                    adj[ind+1].push_back(ind);
                }
                
                if(ind+i < MAX){
                    adj[ind].push_back(ind+i);
                    adj[ind+i].push_back(ind);
                }
                
                if(ind+i+1 < MAX){
                    adj[ind].push_back(ind+i+1);
                    adj[ind+i+1].push_back(ind);
                }
            }
            ind++;
            
            if(ind >= MAX) break;
        }
        if(ind >= MAX) break;
    }
}

void bfs(){
    queue<int> q;
    q.push(a);
    visited[a] = true;
    dist[a] = 0;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        // 종료 조건
        if(now == b) break;
        
        for(int i=0; i<adj[now].size(); i++){
            int nxt = adj[now][i];
            
            if(!visited[nxt]){
                q.push(nxt);
                visited[nxt] = true;
                dist[nxt] = dist[now] + 1;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 피라미드 관계 설정
    setAdj();
    
    cin >> testcase;
    for(int tc=1; tc<=testcase; tc++){
        cin >> a >> b;
        
        memset(visited, false, sizeof(visited));
        memset(dist, 0, sizeof(dist));
        bfs();
        
        cout << "#" << tc << " " << dist[b] << "\n";
    }
    
    return 0;
}