[백준 알고리즘 C/C++] 1005번 문제 풀이 : ACM Craft

** 이 글을 읽음에 앞서 포스팅 된 소스가 100% 정답은 아님을 밝힙니다.

    더욱 유능한 분께서 클린 / 최적의 소스를 짜셨을 가능성이 높습니다.

    기록용으로 남기며, 참고만 부탁드립니다.

** 백준 알고리즘은 직접 풀이를 해보시는 것을 권장합니다.

---

● 문제

난이도[티어] : 골드 3

백준 알고리즘 1005번 문제 ACM Craft

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

---

● 풀이 방법

각 건물들을 지을 수 있는 조건이 랜덤으로 주어지며, 특정 건물을 짓는 데 까지 걸리는 시간을 구해야 한다.

마음같아선 각 모든 건물들이 완공되는데 까지의 시간을 구해버리면 금방이지만, 비효율 적이다.

만약 설계도가 위 처럼 주어지게 되고 특정 건물이 7번이라면 우린 4번 건물이 완공되는 지 여부를 알 필요가 없어지기 때문이다. 

고로 7번 건물을 짓기 위해 필요한 건물들을 찾아내어 각 건물들이 완공되는 시간을 역 추적으로 계산해야 한다.

 

역 추적은 재귀함수를 통해 구현할 수 있다.

---

● 소스 코드

** 소스가 가독성이 떨어진다고 판단됩니다. 더 좋은 클린/최적 소스가 있을 가능성이 높습니다.

#include <iostream>
#include <vector>

// 이 건물이 지어지는데 걸리는 시간 / 총 시간 / 짓기위한 조건을 저장하는 구조체
struct building_info {
    int only_build_time = -1;
    int total_build_time = -1;
    std::vector<int> relate_buildings;
};

// 해당 건물을 짓기 위해 걸리는 총 시간 계산 함수
int total_build_time_cal(int building_num,building_info* B_i)
{
    //이 건물을 짓는데 걸려있는 조건의 개수 파악
    int relate_buildings_cnt = B_i[building_num].relate_buildings.size();
    for(int i = 0; i < relate_buildings_cnt; i++){
        // 이 건물을 짓는데 걸려있는 조건의 건물이 완공되는데 걸리는 총 시간.
        int relate_buildings_total_build_time = B_i[B_i[building_num].relate_buildings[i]].total_build_time;
        // 이 건물을 짓는데 걸려있는 조건의 건물이 완공되는데 걸리는 총 시간이 아직 구해지지 않은 상태라면..?
        if(relate_buildings_total_build_time == -1){
            //이 건물을 짓는데 걸려있는 조건의 건물이 완공되는데 걸리는 총 시간을 구하기 위해 재귀함수 선언
            total_build_time_cal(B_i[building_num].relate_buildings[i],B_i);
        }
    }

    //이 건물을 짓는데 걸려있는 조건의 개수 파악하여 모든 조건이 충족 될 때의 시간을 계산.
    switch(relate_buildings_cnt){
        case 0:
            B_i[building_num].total_build_time = B_i[building_num].only_build_time;
            break;
        case 1:
            B_i[building_num].total_build_time = B_i[building_num].only_build_time + B_i[B_i[building_num].relate_buildings[0]].total_build_time;
            break;
        default:
            int max_relate_build_time = 0;
            for(int i = 0; i < relate_buildings_cnt; i++){
                if(max_relate_build_time < B_i[B_i[building_num].relate_buildings[i]].total_build_time)
                    max_relate_build_time = B_i[B_i[building_num].relate_buildings[i]].total_build_time;
            }
            B_i[building_num].total_build_time = B_i[building_num].only_build_time + max_relate_build_time;
    }
    return B_i[building_num].total_build_time;
}
int main(void)
{
    int test_case; // 테스트 케이스 개수
    int building_cnt; // 건물 개수
    int build_rule; // 건물 규칙(건설 조건) 개수
    int build_rule_start,build_rule_end; // 이 건물이 지어져야(build_rule_start).. 이 건물을 지을 수 있다(build_rule_end).
    int spc_building; // 특정 건물

    std::cin >> test_case;

    for(int i = 0; i < test_case; i++){
        std::cin >> building_cnt >> build_rule;
        struct building_info B_i[building_cnt+1]; // 0번 배열은 공백. -> 건물 번호가 1번 부터 시작하기에 보기 편하게..
        
        for(int i = 1; i < building_cnt+1; i++){
            std::cin >> B_i[i].only_build_time;
        }

        for(int i = 0; i < build_rule; i++){
            std::cin >> build_rule_start;
            std::cin >> build_rule_end;
            //이 빌딩을 짓기 위해 필요한 건물 정보를 저장.
            B_i[build_rule_end].relate_buildings.push_back(build_rule_start);
        }

        std::cin >> spc_building;
        std::cout << total_build_time_cal(spc_building,B_i) << std::endl;
    }
    return 0;
}

 

먼저 건물들의 정보를 구조체 배열 형식으로 선언.

구조체안에 있는 정보는

 1) "이 건물" 하나만 짓는데 소요되는 시간 

 2) "이 건물" 을 짓기 위해 소요된 총 시간

 3) "이 건물을 짓기 위해 완공되어야 할 건물" 번호

1)과 2)는 아직 정보가 입력/계산 되지 않은 상태일 경우를 가정하기 위해 -1로 초기화

건물 규칙은 랜덤으로 주어지기에 3)은 array형식이 아닌 vector형식을 채용.

 

total_build_time_cal 함수의 기능은 크게 두 가지로 구분해서 정의할 수 있다.

 1) "이 건물을 짓기 위해 완공되어야 할 건물"이 완공 되기 까지의 총 시간이 구해져 있는지..?

 2) "이 건물"을 지어지는 데 까지 소요되는 총 시간 계산

 

1)에서 "이 건물을 짓기 위해 완공되어야 할 건물" 이 완공 되기 까지의 총 시간이 구해져 있지 않는다면, 재귀함수를 통해 구함.

즉 특정 건물을 짓기 위해 필요한 건물들을 찾아내어 각 건물들이 완공되는 시간을 역 추적으로 계산하는 구조.

2)에서 "이 건물을 짓기 위해 완공되어야 할 건물" 개수에 따라 "이 건물" 을 지어지는 데 까지 소요되는 총 시간을 산출하는 방식은 3가지 중 하나로 산출 된다.

 

•  CASE 1 : "이 건물을 짓기 위해 완공되어야 할 건물" 개수가 0개 일 때,

가장 처음 지어지는 첫번째 건물이라는 뜻. "이 건물" 이 지어지는 시간이 곧 "이 건물"을 짓기 위해 소요된 총 시간과 같다.

 

•  CASE 2 : "이 건물을 짓기 위해 완공되어야 할 건물" 개수가 1개 일 때,

"이 건물" 짓기 위해 소요된 총 시간은  "이 건물"만 짓는데 소요되는 시간 + "이 건물을 짓기 위해 완공되어야 할 건물" 을 짓기 위해 소요된 총 시간 이다.

 

•  - CASE 3 : "이 건물을 짓기 위해 완공되어야 할 건물" 개수가 2개 이상일 때,

"이 건물" 짓기 위해 소요된 총 시간은  "이 건물"만 짓는데 소요되는 시간 + "이 건물을 짓기 위해 완공되어야 할 건물"들 중 가장 오래 걸리는 완공까지의 소요된 총 시간 이다.

 

vector 라이브러리를 통해 사용한 Part

#include <vector>
// 벡터의 선언
std::vector<자료형> 벡터이름;

// 벡터에 값 넣기
벡터이름.push_back(넣을 값);

// N번째의 벡터 값 출력
std::cout << 벡터이름[N] << std::endl;

 

---

● 결과

** 코드 길이가 상이 할 수 있습니다! 그러나 내용물은 같습니다.

    이유)  주석 및 더미 소스 유무