뚝딱뚝딱

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

💡 Fly me to the Alpha Centauri

✅ 문제 풀이

• 시작지점 x와 끝지점 y의 사이 거리를 구하고, 그 거리는 최소 몇번의 이동이 필요한지 구한다.
• 무조건 처음시작과 마지막 이동은 1씩 이동한다. 따라서 y-x에서 2(처음, 끝)를 뺀 거리만을 가지고 몇번 이동할 수 있는지 구하면 된다.
• 만약 y-x-2의 결과가 0 이하라면, 즉 y-x가 1 또는 2 였다면, 시작과 끝을 제외하고는 중간에서 이동하는 거리가 없기 때문에 1이면 1번 이동하는것이고, 2이면 2번 이동하는 것이된다.
• 다음과 같은 수학적 규칙에 따라 거리마다의 최소 이동 횟수를 구할 수 있다.

• 시작과 끝의 각각 1만큼의 이동 거리를 빼고 생각해보자.
• dis = y-x-2 일때, dis가 1일때부터 이동 횟수를 구해보자. 이때 처음이 1이고, 마지막도 1이었기 때문에, 시작도 마지막도 (0,1,2)에서 고를 수 있게 되어야 한다.
• 1 : 1 => 1
  2 : 2 => 1
  3 : 1,2 => 2
  4 : 2,2 => 2
  5 : 1,2,2 => 3
  6 : 2,2,2 => 3
  7 : 2,3,2 => 3
  8 : 2,2,2,2 => 4
  9 : 2,3,2,2 => 4
  10 : 2,3,3,2 => 4
  11 : 2,3,3,2,1 => 5
  12 : 2,3,3,2,2 => 5
  13 : 2,3,3,3,2 => 5
  14: 2,3,4,3,2 => 5
  15 : 2,3,4,3,2,1 =>6
  16 : 2,3,4,3,2,2 => 6
  17 : 2,3,4,3,3,2 => 6
  18 : 2,3,4,4,3,2 => 6
  ...
  보면, 규칙이 있는걸 확인할 수 있다.
  이동횟수가 1인게 2개, 2인게 2개, 3인게 3개, 4인게 3개.... 
  두 묶음씩 동일한 이동횟수를 갖는 dis의 개수가 하나씩 늘어나고 있다.
  (이동 횟수) => dis의 개수 로 따지면
  (1,2) => 2+2
  (3,4) => 3+3
  ...
  dis의 개수가 같은 것끼리 묶어보면, 4, 6, 8, 10 ...이렇게 늘어나는 것을 알 수 있다.
  이를 누적하면 4, 10, 18, 28....인데, 이 수열을 수식으로 나타내보면 다음과 같다.
  a1 = 4
  a2 = a1+(a1+2)
  a3 = a1+(a1+2)+(a1+2+2)
  a4 = a1+(a1+2)+(a1+2+2)+(a1+2+2+2)
  ...
  an = n*a1+n(n-1) = n*n+3n 으로 정리할 수 있다.
• 이제 dis와 n^2+3n 을 가지고, n=1부터 계산하여 n^2+3n이 dis보다 작으면 n을 늘리고 dis보다 커지면 해당 n을 통해 이동 횟수를 구할 수 있다. 이는 while 문으로 n을 결정할 수 있다
•  이동횟수가 {1,2}인것부터 n=1이고, 그 뒤로 한 묶음씩 n을 늘려가면 된다.
• 예를 들어 dis가 15이면 n=3임을 구할 수 있는데, n*2를 한 6과 n*2-1를 한 5 둘 중 하나가 15의 최소 이동횟수 후보가 된다.
• 근데 n^2+3n-n인 n^2+2n보다 dis가 작으면 n*2-1에 해당하는 5가 답이 되는것이고, 그렇지 않으면 n*2에 해당하는 6이 답이 되는 것이다.

• 따라서 이러한 수학적 규칙과 식을 이용하여 이동 횟수를 쉽게 구할 수 있다.
• 이 문제에서 주의할 점은, 입력으로 주어지는 x와 y의 범위가 2^31까지 이기 때문에, int로 받아 계산하면 안되고, long long으로 받아 계산하여야 한다는 점이다.  

✏ 코드 전문

#include<iostream>

using namespace std;

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

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		long long s, e;//입력단위가 2^31이기 때문에 long long으로 받아야 data손실이 없음!!!
		cin >> s >> e;

		long long n = 1;
		long long dis = e - s - 2;

		if (dis <= 0) {
			cout << dis + 2 << "\n";
			continue;
		}

		while ((n*n + 3 * n) < dis) {
			n++;
		}

		if ((n*n + 2 * n) <= dis) n *= 2;
		else n = n * 2 - 1;

		cout << n + 2 << "\n";
	}

	return 0;
}

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

💡 치킨 배달

✅ 문제 풀이

• 이 문제는 완전탐색을 이용해 조합을 만들어내는 것이 관건이다.
• STL을 사용할 수 도 있지만, 직접 조합을 구해내는 알고리즘이 있다.
• 완전탐색을 이용하면 조합을 구할 수 있다. 
• 만약 치킨 집 총 5개 중에서 3곳만 살려두려고 할 때, 그 세곳으로 정할 수 있는 경우의 수를 구해보자.
• 각 치킨 집을 1-5로 번호를 부여하면, {1,2,3},{1,2,4},{1,2,5}....{3,4,5}로 구할 수 있다.
• 이때 주의할 점은 조합의 경우 순열과 달리 순서를 고려하지 않기때문에 {1,2,3}={2,1,3}이다. 따라서 시작이 2였으면, 1은 고려하지 않기로 한다. 1의 경우는 1이 시작이었을 때 이미 다 선택되었기 때문이다.
• 조합을 구하는 알고리즘에 대한 자세한 설명은 페이지를 참고한다.

• 따라서 나는 다음 순서로 이 문제를 해결하였다.
• 치킨집의 위치를 저장하는 벡터 (chichen)을 생성하여 각 치킨 집의 위치를 저장해주었다. 그리고 벡터의 인덱스를 치킨집 번호로 고려하였다.
• 각 집의 위치를 저장하는 벡터 (home)을 생성하여 각 집의 위치를 저장해주었다. 그리고 벡터의 인덱스를 집의 번호로 고려하였다.
• 치킨집의 조합을 저장하는 벡터 (comb)를 생성하여 조합 결과를 저장해주었다. 이때 치킨집의 인덱스를 번호로 하였다.
• 조합을 구할 때 각 치킨 집의 선택 여부를 고려하기 위한 벡터(visited)를 선언하였다.
• 배열을 입력 받을 때, 값이 1이면 집의 위치를 저장하고, 값이 2이면 치킨집의 위치를 저장하도록 하였다.
• 그리고 입력받은 m개의 치킨집으로만 이루어진 조합을 구하기 위해 DFS함수를 선언하고 호출하였다.

• DFS함수는 조합을 생성한다.
• 각 조합에서 시작 인덱스인 s와 현재 몇개까지 담았는지를 나타내는 cnt를 인자로 갖는다.
• 함수 내에서는 cnt가 m이면, visited의 크기만큼 순회해서 값이 true인 인덱스 = 선택받은 치킨집 을 c라는 임시 vector에 저장하고, m개의 선택된 조합이 담긴 c를 comb에 저장하여 하나의 조합에 대해 저장하도록 했다. 그리고 이 경우에는 수행 후 바로 return하여 함수의 재귀호출을 멈춘다.
• 위에 해당하지 않는다면 인자로 주어진 s 인덱스부터 시작하여 나머지 치킨집을 탐색한다. 이때 현재 치킨집의 visited가 true이면 건너뛰고, 그렇지 않으면 true로 해준뒤, DFS를 재귀호출하고, s는 동일하게, 하지만 방금 현재 인덱스를 선택했으므로 cnt+1을 하여 인자로 넘겨준다. 이를 호출하고 난 뒤에는, 또 선택되어져야 하기 때문에, false로 바꾸어준다.
• 이런식으로 재귀호출을 하다가 cnt가 m이 되는 순간에 조합의 결과를 저장하는 것이다.

• DFS함수를 호출할 때 시작 인덱스는 0, 그리고 현재까지 선택된 치킨집 개수도 0이므로, DFS(0,0)을 호출한다.
• 그런다음, comb에 조합이 다 만들어졌기 때문에, 이제 계산만 하면 된다.
• 모든 집은 각 조합 내에 있는 치킨 집과의 거리 중 최소 거리를 구한다.
• 해당 조합에서 모든 집과 치킨 집과의 누적 거리를 구한다.
• 각 조합 간의 누적 거리들 중 최소 값을 구한다.
• 그 값이 최소 거리가 된다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits.h>//c++17에서는 INT_MAX 정의를 여기서 가져와야해서 필요

using namespace std;
//1. 치킨집의 위치를 갖는 벡터(chicken)를 선언하고 저장해준다. 치킨집의 번호는 인덱스로 구분한다
//2. 일반집의 위치를 갖는 벡터(home)를 선언하고 저장해준다.
//3. 치킨집의 조합을 구한다. 완전탐색으로. 이때 치킨집 번호로 0~chichen.size-1. 조합 결과를 벡터(comb)에 저장한다.

int n, m;
vector<bool> visited;
vector<vector<int>> comb;

void DFS(int s, int cnt) {
	if (cnt == m) {
		vector<int> c;
		for (int i = 0; i < visited.size(); i++) {
			if (visited[i] == true) {
				c.push_back(i);
			}
		}
		comb.push_back(c);
		return;
	}

	for (int i = s; i < visited.size(); i++) {
		if (visited[i]) continue;
		visited[i] = true;
		DFS(i, cnt + 1);
		visited[i] = false;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	int temp;
	vector<pair<int, int>> chichen;
	vector<pair<int, int>> home;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> temp;
			if (temp == 1) {
				home.push_back(pair<int, int>(i, j));
			}
			else if (temp == 2) {
				chichen.push_back(pair<int, int>(i, j));
			}
		}
	}

	visited.resize(chichen.size());

	DFS(0, 0);

	int answer = INT_MAX;//조합에서 가장 최소로 나올 수 있는 값
	for (int i = 0; i < comb.size(); i++) {
		int dis = 0;//각 조합에서의 최소 거리
		for (int j = 0; j < home.size(); j++) {
			int m = INT_MAX;//내집-치킨집 최소 거리
			for (int k = 0; k < comb[i].size(); k++) {
				int index = comb[i][k];//치킨 집 번호
				m = min(m, abs(home[j].first - chichen[index].first) + abs(home[j].second - chichen[index].second));//내 집에서 이 치킨집까지 거리
			}
			dis += m;
		}
		answer = min(answer, dis);
	}

	cout << answer;
	return 0;

}

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

토마토 2차원 배열 입력 문제 풀이 참고

2024.01.22 - [CO-TE/백준] - [백준] 7576번 C++ "토마토" 풀이 / BFS, 너비우선탐색

💡 토마토(3차원 배열 입력 ver.)

✅ 문제 풀이

• 이전에 풀었던 토마토 (7576번) 문제와 풀이 방식은 동일한데, 입력으로 주어지는 차원이 3차원으로 늘어나 높이까지 고려해야 한다.
• 따라서 입력을 받는 arr 벡터도 3차원으로 정의해주었고, 좌표를 담는 queue의 자료형도 pair를 한번 더 감싸서 3개의 int 쌍을 갖도록 하였다.
  => pair<pair<int,int>,int>
• 입력으로는 한 판 씩 맨 아래 층 부터 들어오기 때문에 for문의 시작에 for문을 하나 더 추가해서 높이마다 한판 씩 정보를 입력 받도록 하였다.
  = 마지막에 확인할 때도 맨앞에 높이에 대한 for문만 추가해주었다.
•  queue에 push할때도 queue의 자료형에 맞게 두 개의 pair 쌍으로 값을 입력해주었다. 여기서 x 와 y 는 전체 pair에서도 첫번째인 pair 쌍에 해당하기 때문에 front().first.first, front().first.second 로 두번씩 들어가 접근하도록 하였고, z는 전체 pair에서 두번째 값이기 때문에 front().second로 접근하도록 하였다.
• 높이에 대한 조건이 추가되면서, 인접한 범위가 위, 아래 까지 늘어났다. 따라서 총 6번의 탐색을 해야하므로, bfs 함수내에서 사용하는 dx, dy를 수정해주었다. 맨뒤에 높이에 대한 변화가 없도록 {0,0}을 추가해준다. 그리고 높이에 대한 dz를 추가해주고, {0,0,0,0,-1,1} 으로 높이에 대해서만 변화가 있도록 한다.
• bfs 함수 내에서 탐색은 4->6으로 수정해주고, 함수의 인자로는 x,y 뿐만 아니라, z도 받도록 하여, 전체 위치를 표시해준다.
• arr의 인덱스 범위에서도 z는 0이상 h이하에 있도록 검사한다.
• 나머지 로직은 동일하다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n, m, h;
vector<vector<vector<int>>> arr;
queue<pair<pair<int, int>,int>> q;
queue<pair<pair<int, int>,int>> temp;

int dx[] = { -1,1,0,0,0,0 };
int dy[] = { 0,0,-1,1,0,0 };
int dz[] = { 0,0,0,0,-1,1 };

int answer = 0;

void bfs(int x, int y, int z) {
	for (int i = 0; i < 6; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		int nz = z + dz[i];

		if (nx >= 0 && nx < n&&ny >= 0 && ny < m&& nz>=0 && nz< h&& arr[nx][ny][nz] == 0) {
			arr[nx][ny][nz] = 1;
			temp.push(pair<pair<int, int>, int> (pair<int, int>(nx, ny),nz));
		}
	}
}

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

	cin >> m >> n >> h;

	arr.resize(n, vector<vector<int>>(m, vector<int> (h)));

	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> arr[i][j][k];
				if (arr[i][j][k] == 1) {
					q.push(pair<pair<int, int>, int> (pair<int, int> (i, j), k));
				}
			}
		}
	}

	while (!q.empty()) {
		bfs(q.front().first.first, q.front().first.second, q.front().second);
		q.pop();
		if (q.empty()) {//한번 돌았음을 의미
			answer++;
			while (!temp.empty()) {
				q.push(pair<pair<int, int>, int> (pair<int, int> (temp.front().first.first, temp.front().first.second),temp.front().second));
				temp.pop();
			}
		}
	}

	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j][k] == 0) {
					cout << -1;
					return 0;
				}
			}
		}
	}

	cout << answer - 1;

	return 0;
}

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

💡 하노이 탑 이동 순서

✅ 문제 풀이

• 하노이 탑 문제는 재귀호출을 통해 풀이 할 수 있다.
• 하노이 탑의 다음과 같은 공식 때문이다.
• 탑 1에 있는 가장 작은 원판을 탑 3으로 옮긴다. 탑 3에 있는 가장 작은 원판을 탑 2로 옮긴다. 탑 2에 있는 가장 작은 원판을 탑 1로 옮긴다. 탑 1에 있는 가장 작은 원판을 탑 3으로 옮긴다.
• k-1개의 원판은 위 공식을 따르게 된다. 
• 따라서 각 원판을 재귀 호출을 통해 이동 순서를 표현할 수 있다.
• 정리하자면, 1->3->2, 2->1->3 순서로 이동하게 된다.
• 이를 위해 hanoi라는 함수를 선언해준다.
• 이 함수는 현재 원판의 번호(=크기)와 시작(from), 중간(by), 끝(to) 지점을 인자로 갖는다.
  만약 원판의 번호가 1이면 "from to"을 출력하도록 한다.
  그렇지 않다면 hanoi를 호출하고 인자로 원판의 번호-1, from, to, by 순서로 넣어준다. 이는 1->3->2 순서를 나타낸 것이다.
  그리고 이 함수를 호출한 후에는 "from to"를 호출하여 이동 상황을 출력한다.
  그다음, hanoi를 한번 더 호출하여 인자로 원판의 번호-1, by, from, to 순서로 넣어준다. 이는 2->1->3 순서를 나타낸 것이다.
• 따라서 원판 하나에 대해 hanoi 함수는 두번 재귀호출 하므로, 연산이 2^k번 발생하는데, 가장 큰 원판은 바로 이동할 수 있으므로 1을 빼준다. 따라서 총 이동 횟수는 2^k-1이 된다.
• 참고로 c++의 경우, pow함수를 사용할 때 int로 형변환을 해주지 않으면 결과가 틀렸습니다가 나오므로, int로 꼭 변환한 후 -1을 빼주도록 한다. (pow함수의 반환 형태는 double 형이기 때문) 

✏ 코드 전문

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

using namespace std;

void hanoi(int n, int from, int by, int to) {
	if (n == 1) {
		cout << from << " " << to << "\n";
	}
	else {
		hanoi(n - 1, from, to, by);
		cout << from << " " << to << "\n";
		hanoi(n - 1, by, from, to);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int k;
	cin >> k;

	cout << int(pow(2, k)) - 1 << "\n";
	hanoi(k, 1, 2, 3);

	return 0;
}

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

💡 토마토

✅ 문제 풀이

• BFS를 활용하는 문제이다.
• queue를 사용하여 방문해야 할 곳을 pair<int,int> 형태의 좌표를 저장하도록 하였다.
• 먼저 토마토에 대한 2차원 배열을 순회하면서 값이 1이면 그 위치를 q라는 queue에 pair<int,int> 형태로 넣는다.
• 모두 탐색한 후에는 while문으로 q가 빌때까지 bfs를 수행한다.
• q에서 가장 앞에 있는 front의 first와, second를 bfs의 인자로 넘겨준다.

• BFS함수의 동작
  1. 인자로 받은 위치를 가지고, 동 서 남 북 방향에 있는 값이 배열의 인덱스 범위에 유효하며, 값이 0인지 확인한다.
  2. 위의 조건을 만족한다면 해당 위치의 arr값을 1로 변경해주고, temp라는 이름의 queue에 해당 위치를 pair<int,int> 형태로 넣어준다.

• BFS함수를 돌고 나면 q에서 pop한다.
• 그런다음, 현재 q가 비어있다면, 하루에 익을 수 있는 토마토는 다 익은 것이므로 하루를 카운트 하기 위해 answer를 1 증가시킨다.
• 새로 익어진 토마토에 대한 정보를 가진 temp 있는 위치 정보들을 q에 다 옮겨놓는다.
• 그리고나서 이어지는 다음 while문 동작부터는 다음 날짜에 대한 동작을 진행하는 것이다.
• 그런데, q가 비어지게 되면 temp가 비어있고, 그날이 마지막 날이었더라도 하루가 무조건 더해지게 되기 때문에, 마지막에는 answer에서 1을 뺀 값이 답이된다.
• while문을 모두 수행하고 나면, 갱신된 2차원 배열을 순회하면서, 하나라도 0이 있는 값이 있는지 찾아본다.
• 이는 0이 하나라도 있다면 모든 토마토가 익어질 수 없다는 뜻이므로 -1을 출력하고 프로그램을 종료하기 위함이다.
• 그렇지 않다면 answer-1을 출력하도록 하여, 토마토 판에서 토마토가 다 익는데 걸리는 날을 출력한다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n, m;
vector<vector<int>> arr;
queue<pair<int, int>> q;
queue<pair<int, int>> temp;

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int answer = 0;

void bfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&arr[nx][ny] == 0) {
			arr[nx][ny] = 1;
			temp.push(pair<int, int>(nx, ny));
		}
	}
}

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

	cin >> m >> n;

	arr.resize(n,vector<int>(m));

	bool end = true;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				q.push(pair<int,int>(i, j));
			}
		}
	}

	while (!q.empty()) {
		bfs(q.front().first, q.front().second);
		q.pop();
		if (q.empty()) {//한번 돌았음을 의미
			answer++;
			while(!temp.empty()) {
				q.push(pair<int,int>(temp.front().first, temp.front().second));
				temp.pop();
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {
				cout << -1;
				return 0;
			}
		}
	}

	cout << answer-1;

	return 0;
}

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

💡 ACM Craft

서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.
이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.

위의 예시를 보자.
이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.
따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.
프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

[입력]
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 
둘째 줄에는 각 건물당 건설에 걸리는 시간 D1, D2, ..., DN이 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 
마지막 줄에는 백준이가 승리하기 위해 건설해야 할 건물의 번호 W가 주어진다.

[출력]
건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다.
건설순서는 모든 건물이 건설 가능하도록 주어진다.

문제를 요약하자면..

1번부터 N번까지의 N개의 건물이 있을 때, 주어진 건설 순서 (1 2 = 1->2) 에 따라서 각 건물이 건설될 수 있다.

예를 들어 앞의 그림에 따르면, 2와 3은 1이 건설된 후에야 건설할수 있고, 4는 2와 3이 모두 건설된 후에야 건설할 수 있다.

각 건물을 건설하는데에는 DN의 시간이 소요되고, 입력으로 주어진다.

이때 입력으로 받는 건물 W를 건설하는데 소요되는 최소시간을 구하는 문제이다.

✅ 문제 풀이

W를 건설하기 위해서는 W하위에 연결된 모든 건물이 완료되어야 하기 때문에, W까지 연결되는 여러 경로 중 에서 소요되는 시간이 최대일 때와 같다.

=> 왜 최대이냐?

W가 건설되기 전까지는, W를 건설하기 위해 먼저 건설되어야 하는 건물들 모두가 건설을 마쳐야 W를 건설할 수 있기 때문에, 위의 예시처럼 건물 2가 1초 밖에 걸리지 않다 하더라도, 건물4가 건설되려면 건물3도 건설되어야 하므로, 둘 중 더 소요시간이 긴 건물 3에 의해 100초가 더해져야 한다. 따라서 총 10초(건물1)+100초(건물2,3)+10초(건물4)=120초가 소요된다.

따라서 이 문제는 위상정렬을 이용해서 해결할 수 있다.

다음 사항들을 고려해야 한다.

1. 각 건물(노드)을 건설한 바로 다음에 건설될 수 있는 건물들을 저장해야 한다.
=> vector<int> node[1005]를 vector 타입의 배열을 만들어서, 각 노드(인덱스=건물번호)에 이전 건물에 대한 정보를 vector로 추가해준다.

2. 각 건물까지 짓는데 걸리는 최소 시간을 저장하는 배열이 있어야 한다.

=> vector<int> sum(1005,0); 
=> 각 노드(인덱스=건물번호)에 저장한다.

3. 각 건물에 대한 깊이를 저장하는 배열이 있어야 한다.
=> 예시에서 보면 1은 선행 노드가 없으므로 깊이가 0, 2와 3은 선행노드가 1이 있으므로 1, 4는 선행노드가 1, 2-3이 있으므로 2이다. 

=> vector<int> degree(1005,0)

이제 코드를 하나씩 만들어가 보자.

• 테스트 케이스 T를 받아 저장한다.
• T번의 테스트 케이스를 진행하도록 for문을 작성하고, for문 안에서 아래 내용들이 동작하도록 구현한다.
• 건물을 개수를 입력받아 N에 저장한다.
• 건설 규칙의 개수를 입력받아 K에 저장한다.
• 다음을 미리 선언해준다.
  ✔ vector<int> D(1005,0) : 각 건물의 건설시간을 담은 크기가 1005인 벡터 D
  ✔ vector<int> sum(1005,0) : 각 건물을 완성하기까지 걸리는 시간을 담은 크기가 1005인 벡터 sum
  ✔ vector<int> node[1005] : 각 건물의 후행 건물을 담은 벡터 타입의 크기가 1005인 배열 node
  ✔ vector<int> degree(1005,0) : 각 건물(노드)의 깊이를 담은 크기가 1005인 벡터 degree
  =>값은 모두 0으로 초기화 
• 각 건물의 건설시간을 건물 번호에 맞게 차례로 입력받는다.
  => 벡터 D의 1번 인덱스부터 1번 건물의 건설 시간을 입력받아 저장한다.
  => 그리고 sum의 동일한 인덱스에 입력받은 각각의 건설 시간을 저장해준다. sum에는 일단 각 건물에 대한 건설시간이 저장되어 있는 것이다. = 만약 맨 아래 노드라면 해당 건물을 짓는데는 해당 건물의 건설시간만 소요될 것이므로 미리 값을 지정해준다.
• K개의 건설 규칙을 입력받자. for문을 연다.
• 건설 규칙을 입력받기 위해 선행 건물을 저장하는 x와, 후행 건물을 저장하는 y를 선언하고, 입력받아 저장한다.
• node[x]에다가 y를 넣어준다. 현재 이 배열은 벡터 타입이므로 push_back하여 y를 저장한다.
•  그리고 y 이전에 x가 먼저 건설되기 때문에, y는 선행 노드가 있다는 것이므로, degree[y]를 1 늘려줘서 깊이를 1 높인다.
• 이렇게 K개의 규칙에 대해 다 실행한 후 for문이 끝나면 경로를 하나씩 접근해가며 sum을 갱신할 수 있다.
• 그 전에 W를 입력받아서 저장해둔다.모든 건물의 sum을 구한 후 그중 sum[W]를 통해 W건물까지 짓는데 걸리는 최소시간을 구할 수 있다. 다음을 진행하여 sum을 설정하자.
• queue<int> q를 하나 생성하여 방문할 노드들을 저장하는 용도로 사용하자.
•  일단 모든 건물(=노드)를 for문을 통해 돌아보면서, 현재 노드의 degree가 0인지 확인한다.
• 현재 노드의 degree가 0이라면, 선행 노드가 없다는 것이므로, q에 현재 노드를 push한다.
• for문을 다 돌면, while문을 통해 q가 빌 때 까지 다음을 수행한다.
• q의 맨 앞에 있는 노드를 꺼내 top에 저장한다. 그리고 node[top]에 저장된 모든 후행 노드를 순회하면서 next에 저장한다.
• 만약 sum[top]+D[next] 가 sum[next]보다 크다면 sum[next]를 전자로 갱신시켜준다. =>이게 바로 같은 레벨에서는 최대로 걸리는 값으로 갱신해야 한다는 의미이다. 같은 레벨에 있는 건물은 다음 건물 짓기 전에 모두 건설완료되어야 하기 때문에 가장 오래 걸리는 건설 시간을 반영한다는 뜻이다.
• 그리고 degree[next]를 1 줄여서 선행 노드를 이미 방문했음을 표시한다.
• 그리고 degree[next]가 0이면 이 노드를 시작으로 위 과정을 반복하기 위해 q에 push한다.
• 그럼 while문을 충족하므로 과정을 반복한다.
• 맨 마지막 노드에서 degree[next]를 1 줄임으로써 0이 되면서 while문이 종료되고, 각 노드에 대한 최종 sum이 설정되었을 것이다.
• 그럼 이때 sum[W]를 출력하여 프로그램을 마친다. 

☑ 코드 전문

#include<iostream>
#include<string>
#include<vector>
#include<queue>

using namespace std;

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

	int T;
	cin >> T;

	for (int i = 0; i < T; i++) {
		int N, K, W, top, next;
		vector<int> D(1005, 0);//각 건물의 건설시간
		vector<int> node[1005];//노드 별 이어지는 노드 
		vector<int> degree(1005, 0);//루트로부터 몇번째에 있는지
		vector<int> sum(1005, 0);//현재 노드까지의 총 건설 시간
		queue<int> q;

		cin >> N >> K;
		for (int j = 1; j <= N; j++) {
			cin >> D[j];
			sum[j] = D[j];
		}
		for (int j = 0; j < K; j++) {
			int x, y;
			cin >> x >> y;
			node[x].push_back(y);
			degree[y]++;
		}

		cin >> W;
		for (int j = 1; j <= N; j++) {
			if (!degree[j]) {//내 아래로 없으면
				q.push(j);//이 노드의 후행 노드들을 살펴보자
			}
		}
		while (!q.empty()) {
			top = q.front();
			q.pop();
			for (int j = 0; j < node[top].size(); j++) {
				next = node[top][j];
				if (sum[top] + D[next] > sum[next]) sum[next] = sum[top] + D[next];
				degree[next]--;
				if (!degree[next]) q.push(next);
			}
		}

		cout << sum[W]<<"\n";

	}
	return 0;
}