[C++] 백준 1005번 탈출

1005번: ACM Craft

 

그래프 탐색과 DP를 통해 해결할 수 있는 문제.

특정 건물을 짓기 위해 어떻게 빨리 지을 수 있는 지 알아내는 알고리즘을 작성하는 문제였다.

알고리즘 분류를 보니, 위상 정렬이라는 알고리즘이 있었는데 해당 알고리즘에 대해서는 내가 아는 바가 없었지만

풀 수는 있었다.

 

문제 풀이

예시 이미지를 통해 문제를 해석해 보았다.

• 4번 건물을 짓기 위해서는 10초의 시간이 필요하며,
  2번과 3번의 건물이 지어져 있어야 한다.
  
  
• 2번 건물을 짓기 위해서는 1초의 시간이 필요하며,
  1번 건물이 지어져 있어야 한다.
  
  
• 3번 건물을 짓기 위해서는 100초의 시간이 필요하며,
  1번 건물이 지어져 있어야 한다.
  
  
• 1번 건물을 짓기 위해서는 10초의 시간이 필요하며,
  바로 지을 수 있다.

 

그렇다면 고려해야 할 사항은 다음과 같았다.

1. 만일 1번 건물의 경우 지금은 한 번만 탐색하지만, Depth가 깊어진다면?
   -> 2번 건물과 3번 건물이 1번 건물의 건설시간을 탐색할 때 시간이 길어진다.
   
   
2. 우선적으로 건설되어야 하는 건물들 중 가장 오래 걸리는 시간이 그 이전 단계에서
   진행되어야 하는 건설 시간이다.

 

번의 경우, 동적 프로그래밍에서 메모 기법을 통해 해결할 수 있었고,

2번의 경우에는 자식들 중 최대로 오래 걸리는 시간을 check해주면 됐다.

 

코드

/*
* 백준 1005번 ACM Craft
* https://www.acmicpc.net/problem/1005
* 다이나믹 프로그래밍 / 그래프 탐색
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int tCnt, buildingCnt, ruleCnt, goalNum;
int buildTime[1001];
int totalBuildTime[1001];
vector<int> prevBuildingNumVec[1001];

int check(int num) {

    int prevTime = 0;

    for (int num : prevBuildingNumVec[num]) {
        if (totalBuildTime[num] != -1) {
            prevTime = max(prevTime, totalBuildTime[num]);
        }
        else {
            prevTime = max(prevTime, check(num));
        }
    }

    totalBuildTime[num] = buildTime[num] + prevTime;

    return totalBuildTime[num];
}

int main() {
    cin >> tCnt;

    while (tCnt--) {
        cin >> buildingCnt >> ruleCnt;

        for (int i = 1; i <= buildingCnt; i++) {
            cin >> buildTime[i];
            totalBuildTime[i] = -1;
            prevBuildingNumVec[i].clear();
        }

        int prevNum, nxtNum;
        for (int i = 1; i <= ruleCnt; i++) {
            cin >> prevNum >> nxtNum;

            prevBuildingNumVec[nxtNum].push_back(prevNum);
        }

        cin >> goalNum;

        cout << check(goalNum) << "\n";
    }

    return 0;
}

 

변수

int tCnt, buildingCnt, ruleCnt, goalNum;
int buildTime[1001];
int totalBuildTime[1001];
vector<int> prevBuildingNumVec[1001];

• tCnt, buildingCnt, ruleCnt, goalNum : 각각
  테스트 케이스, 건물 갯수, 조건 갯수, 목표하는 건물 번호
  
  
• buildTime 배열 : 해당 번호의 건물'만' 짓는데 걸리는 시간
  
  
• totalBuildTime 배열 : 해당 번호를 짓는데 필요한 건물들까지 다 짓고 해당 건물까지 짓는 데 걸리는 시간
  
  
• prevBuildingNumVec 벡터 : 해당 번호의 건물을 짓는 데 필요한 건물들의 번호를 저장하는 벡터

 

메인 함수

int main() {
    cin >> tCnt;

    while (tCnt--) {
        cin >> buildingCnt >> ruleCnt;

        for (int i = 1; i <= buildingCnt; i++) {
            cin >> buildTime[i];
            totalBuildTime[i] = -1;
            prevBuildingNumVec[i].clear();
        }

        int prevNum, nxtNum;
        for (int i = 1; i <= ruleCnt; i++) {
            cin >> prevNum >> nxtNum;

            prevBuildingNumVec[nxtNum].push_back(prevNum);
        }

        cin >> goalNum;

        cout << check(goalNum) << "\n";
    }

    return 0;
}

메인함수에서는 특별한 로직은 없고,

• 건물 갯수, 조건 갯수를 입력받는다.
• 건물 갯수만큼, 해당 건물의 건설시간을 입력받고 
  총 건설시간 배열, 이전 조건의 번호 벡터를 초기화해준다.
  -1로 초기화하는 이유는 건설 시간이 0초가 될 수 있기 때문이다.
  
  
• 그리고 건물의 조건 수만큼 조건들을 입력받는다.
  
  
• 마지막으로 목표하는 건물의 번호를 입력받고,
  check(목표 번호)의 결과를 출력한다.

 

건물 건설 시간 구하는 메서드

int check(int num) {

    int prevTime = 0;

    for (int num : prevBuildingNumVec[num]) {
        if (totalBuildTime[num] != -1) {
            prevTime = max(prevTime, totalBuildTime[num]);
        }
        else {
            prevTime = max(prevTime, check(num));
        }
    }

    totalBuildTime[num] = buildTime[num] + prevTime;

    return totalBuildTime[num];
}

해당 건물을 짓는 데 이전 건물들을 짓는 데 필요한 시간을 prevTime에 저장해둔다.

그리고 이전 건물들을 보면서,

만일 해당 건물을 짓는 데 필요한 시간이 구해지지 않았다면(-1이라면) check 메서드를 통해 구하게 하고,

구해져 있다면 바로 해당 건물을 짓는데 필요한 시간을 사용한다.

 

다 구했다면, 배열에 기록한 후 값을 return해준다.

 

이전부터 풀어야지 풀어야지 생각만 하고 못 풀고 있었는데 오늘 겨우야 풀었다.

생각보다 쉽게 풀려서 놀랐다.