[백준/c++] - 1005 ACM Craft

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

1005번: ACM Craft

 

 

목차
1. 문제 풀이
2. 코드

 

 

문제풀이

  처음에는 문제 분류가 dp로 되어 있어서 왜 dp로 풀리는 지에 대해 고민해 보았다. 건물의 건설은 주어진 순서대로 진행해야 하기에 그리디 방식으로 단순하게 구현하면 되지 않을까하고 생각해 보았으나, 건물이 지어지는 순서를 제대로 파악하기 힘들뿐만 아니라, 문제에서 무조건 마지막에 지어지는 건물의 건축 시간만 물어보는 게 아니므로 모든 건물에 대해 최소 시간을 정리할 필요가 있었다. 따라서 dp로 다시 접근하였다.

 

 

 

 

 

 결과적으로 먼저 지어지는 건물에 대해 최소 시간들을 구하고 그 값을 이용해서 그 후에 지어지는 건물들의 최소 건축 시간을 알 수 있으므로 dp로 접근하는 것이 옳은 방법이라 판단하였다.

 

 

 

 

 

 주어진 그림이 그래프 형태로 주어져 있기에 인접 리스트 방식으로 데이터를 정리하였다. 그 후 모든 노드를 번호 순서대로 돌면서 자신(n) 이전의 건물들 중에 가장 최대 값을 찾아 자신의 건축 시간을 더하여 dp[n] 값을 구하도록 하였다.

 

 

 

 

 

 

 

 다만 예제를 자세히 보니 무조건 번호 순서대로 건물들을 짓는 순서가 정해지는 게 아니란 것을 알게 되었다. 즉 규칙에 따라 1번 건물이 가장 나중에 지어질 수 도 있다는 것이다.

 

 

 

 

 

 

 

 이러한 문제점을 깨달은 후, BFS DFS 방식에서 사용하는 방문체크용 배열을 하나 선언하여 자신 이전의 건물(노드)이 지어졌는지(방문했는지) 체크하는 방식으로 모든 건물이 지어질 때까지 반복문을 돌리는 방식으로 교체하여 건물 번호와 상관없이 주어진 조건대로 모든 건물이 지어질 수 있도록 하였다.

 

 

 

 

 

 마지막으로 인접 리스트 방식으로 표현하였으므로 게임을 시작하자 마자 지을 수 있는 건물은 size() 값이 0이므로 이를 이용하여 dp의 초기값을 세팅할 수 있다.

 

 

 

코드

#include<iostream>
#include<math.h>
#include <queue>
#include <climits>
#include <iostream>

using namespace std;

// 노드(건물)의 최대 수는 1000, 엣지의 최대 개수는 100000개
// 시간 복잡도 n^2은 불가능
// dp로 해결이 가능한가? -> 무조건 마지막 건물에 대해 묻는 문제가 아니다.
// 즉, 모든 건물에 대해 최소 시간을 구해야할 필요가 있다.

// dp로 문제를 접근하면 모든 건물에 대해 최소 시간을 구하고, 그 결과 값을 이용하여
// 다음 건물의 최소 건설 시간을 구하는 방식으로 접근할 수 있다.

// 건물은 인접리스트 방식으로 표현


// 문제점: 건물의 건설 시작 순서는 노드 번호대로가 아니다 -> 이전 건물을 지었는지, 얼마나 걸려야 최소인지 구분이 안된다.
// -> 건설(방문)완료 배열을 만들어서 따로 관리를 해준다, 입력 값으로 주어지는 리스트를 반대로 연결하여 이전 건물의 건설 시간 중 최대가 되는 것에 자신의 건설 시간을 더하여 해결해 주자.

// dp[n] = max(자신으로 향하는 노드들 중 가장 큰 dp값) + 자신의 건설에 걸리는 시간

int T;


void input() {
	cin >> T;
}


int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	input();
	
	for (int test = 0; test < T; test++) {
		int N, K; // 노드 수, 엣지 수

		vector<int>craftTime; // 건설에 걸리는 시간
		vector<vector<int>> map; // 노드 그래프
		bool check[1001]{ false, }; // 건설(방문)노드
		int dp[1001]{ 0, }; // 이전 노드들 중 가장 건설시간이 오래 걸리는 것 + 자신

		

		cin >> N >> K;

		craftTime.push_back(0); // 더미 값
		for (int i = 0; i < N; i++) {
			int cTime;
			cin >> cTime;
			craftTime.push_back(cTime);
		}

		map.resize(1001);
		for (int i = 0; i < K; i++) {
			int start;
			int end;
			cin >> start >> end;

			map[end].push_back(start); // 인접 리스트를 반대로 연결하여 자신을 향하는 노드들을 찾기 쉽도록 한다.
		}

		// 무조건 1번 노드부터 고정적으로 건설하지 않는다.
		// 가장 처음에 지어지는 건물을 알아야한다.
		// -> 방문 배열을 만들고 모든 이전 노드가 방문 완료인 상태에서만 건설을 시작 + 인접노드가 존재하지 않는다면 바로 건설 시작
		
		// 기본값 갱신
		for (int i = 1; i < N; i++) {
			if (map[i].size() == 0) { // 자신으로 향하는 노드가 없다면 바로 갱신
				dp[i] = craftTime[i];
				check[i] = true;
			}
		}


		// 모든 노드를 돌며 건설을 진행
		// 시작 노드를 기준으로 계속 다음 노드로 나아가야 한다.
		bool flag = true;
		while (flag) {
			// 모든 노드를 돌며 dp값 갱신
			flag = false;
			for (int i = 1; i <= N; i++) {
				if (check[i] == false) { // 아직 건설 안한곳에 한해서만
					// 건설할 수 있는가?
					bool craftEnable = true;
					int maxVal = 0;
					for (int j = 0; j < map[i].size(); j++) {
						if (check[map[i][j]] == false) { // 아직 건설 불가
							craftEnable = false;
							break;
						}
						maxVal = max(maxVal, dp[map[i][j]]); // 이전 노드들의 건설 시간 중 가장 큰 것
					}

					if (craftEnable) {
						dp[i] = maxVal + craftTime[i]; // dp 값 갱신
						check[i] = true; // 방문(건설) 완료
					}
						

					flag = true; // 변화가 일어났으므로 한번 더 진행
				}


			}

		}



		// 정답 출력
		int W;
		cin >> W;
		cout << dp[W] << "\n";
	}

	


	return 0;
}