굳건하게

문제 : https://www.acmicpc.net/problem/15681

문제해석

 루트가 정해진 트리가 주어졌을 때, 임의의 노드의 SubTree의 크기를 구하자.

 이때, 트리가 이진트리! 라는 말이 없으므로 조심해야한다.

문제핵심

 이 문제의 핵심은 SubTree의 크기를 구해야되는 쿼리가 10^5번 들어올 수 있기 때문에, 처음에 Root부터 시작해서 모든 노드의 SubTree의 크기를 구해둬야한다. ( 그렇게 안해도 시간 초과가 안나오는지는 모르겠습니다! ) 쿼리마다 구하면 아마 시간초과가 나올 것 같다.

알고리즘

 TreeDp를 이용해서 Root 부터 시작해서 재귀적으로 모든 노드들의 SubTree 의 크기를 구해야한다. 현재 노드가 연결된 노드들이 이미 다 방문한 노드라면, 해당 노드는 leaf 노드 이므로 Dp 값은 0이고, 1을 return 해주면 된다. leaf 노드가 아니라면 자식 노드들의 subTree 값을 모두 더해서 저장하고, 자기 자신을 포함해서 subTree + 1 값을 return 해주면 된다.

문제 : https://www.acmicpc.net/problem/18235

문제해석

 1 ~ N 까지 좌표들이 있고, 오리 두마리가 A 와 B 지점에서 시작해서 하루에 한 번 점프를 해가며 이동한다. 점프를 안하는 경우는 없고,  점프 크기는 1부터 시작해서 2배씩 늘어난다. 이때, 둘이 만날 수 있는지, 만난다면 몇 일이 지나고 만나는지를 구하는 프로그램을 작성하라.

문제핵심

 1. 점프 크기가 2배씩 늘어나므로 19일에 점프크기는 262,144(2^18)가 되고 N이 최대 500,000이므로 20일부터는 의미가 없어진다. 왜냐하면 20일 부터 점프 크기가 500,000보다 크므로 점프를 하면 어차피 범위를 벗어나게 된다. 따라서, 우리는 19일까지만 시뮬레이션을 진행해보면 된다. --> 19 * O(N) 으로 처리하자.

 2. 우리는 k 일에 A 오리와 B 오리가 갈 수 있는 모든 지점을 알고 있다면, (k + 1) 일에 A 오리와 B 오리가 갈 수 있는 모든 지점을 구할 수 있다. --> 모든 지점을 저장해가면서 진행해보자.

알고리즘

 문제핵심 1, 2번에 의해서 현재 A, B 오리가 도착한 지점을 통해 다음 A, B 오리가 도착한 지점을 저장해나가며 문제를 해결할 수 있다. 메모리를 조금이라도 아끼기위해 bool 배열과 flag 기법을 이용해서 저장해나갔다.

 day 0부터 시작해서 day가 짝수라면 visited[0] 에 현재 방문한 지점들이 있고, visited[1] 에 다음에 방문할 지점들을 check 해가며 문제를 해결했다.

 1) 현재 방문한 지점들 중에 겹치는 곳이 있는지. --> 있다면 오리가 만났다!

 2) 다음에 방문한 지점을 저장할 공간을 초기화한다.

 3) 현재 지점을 토대로 다음에 방문할 지점을 계산해 저장한다.

알고리즘회고

처음에는 2개의 deque를 이용해서 현재 A 오리가 갈 수 있는 모든 지점을 저장하고, B 오리가 갈 수 있는 모든 지점을 저장하고, deque의 앞에서부터 현재 지점들을 뽑아가며 jump 를 +, jump 를 - 해서 다음 지점들을 다시 deque의 뒤로 push 했다. 당연히 deque의 push, pop 이 굉장히 많이 일어났고, 현재 지점들에서 같은 지점이 있는지 없는지 체크를 위해 2개의 deque을 2중 for문으로 순회해야되서 시간초과를 맛보게 되었다. 따라서, 메모리를 조금 더 사용하고 deque을 사용하지 않는 방식으로 알고리즘을 갈아엎었다.

문제 : https://www.acmicpc.net/problem/15591

Graph BFS

 a 동영상과 b 동영상의 relevant 값은 a에서 b로 가는 경로 중 간선의 값이 가장 작은 값이 됩니다. 우리는 k와 v가 주어질 때마다, v번 동영상에서 다른 모든 동영상까지 relevant 값이 k 이상인 동영상들을 count 해줘야합니다. 따라서, a 동영상에서 시작해서 BFS 탐색을 진행하면서 다른 모든 동영상과의 relevant 값을 구하면 되는데, a에서 어떤 동영상까지 탐색하는데 relevant 값이 주어진 k보다 작아진다면, 그 뒤의 탐색들도 다 k보다 relevant 값이 작아지므로 탐색을 마저 진행하지 않는다.

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

using namespace std;

int N, Q, p, q, r, k, v;
vector<pair<int, int>> map[5001];

int BFS(int k, int v) {
	int ans = 0;
	vector<bool> visited(5001, false);
	queue<int> q;
	q.push(v);
	visited[v] = 1;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < map[cur].size(); i++) {
			int next = map[cur][i].first;
			int relev = map[cur][i].second;
			if (!visited[next] && k <= relev) {
				visited[next] = 1;
				q.push(next);
				ans++;
			}
		}
	}
	return ans;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> Q;
	for (int i = 0; i < N - 1; i++) {
		cin >> p >> q >> r;
		map[p].push_back({ q, r });
		map[q].push_back({ p, r });
	}
	for (int i = 0; i < Q; i++) {
		cin >> k >> v;
		cout << BFS(k, v) << '\n';
	}

	return 0;
}

문제 : https://www.acmicpc.net/problem/10021

MST Graph Prim

 N개의 노드가 존재하고, a 노드에서 b 노드로 가는 간선이 존재하려면, 거리가 C 이상이여야 됩니다. 우리는 모든 노드들이 서로 연결되어있는 상태를 최소 비용으로 만들고 싶으므로, MST를 만들면 됩니다.

 MST 알고리즘은 대표적으로 Prim, Kruskal 2개가 있는데 이 문제는 간선이 굉장히 많이 존재할 수 있는 밀집 그래프 문제이므로 Kruskal로 MST를 구하면 시간초과를 직면하게 되고, Prim 알고리즘을 사용해야된다.

1) 모든 노드를 순회하며 거리를 계산하고, 거리가 C 이상이면 graph 에 간선을 만들어준다.

( 간선은 양방향 )

2) Prim 알고리즘을 통해 MST를 구한다.

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

const int INF = 1000000001;

int N, C;
int graph[2000][2000];
pair<int, int> point[2000];
int dist[2000];
bool selected[2000];

int getDist(int i, int j) {
	return (int)pow(point[i].first - point[j].first, 2) + (int)pow(point[i].second - point[j].second, 2);
}

int get_min_vertex() {
	int v;
	for (int i = 0; i < N; i++) {
		if (!selected[i]) {
			v = i;
			break;
		}
	}
	for (int i = 0; i < N; i++)
		if (!selected[i] && (dist[i] < dist[v])) v = i;
	return v;
}

int prim(int s) {
	for (int i = 0; i < N; i++)
		dist[i] = INF;
	dist[s] = 0;
	for (int i = 0; i < N; i++) {
		int u = get_min_vertex();
		selected[u] = 1;
		if (dist[u] == INF) return -1;
		for (int j = 0; j < N; j++)
			if (graph[u][j] != INF && !selected[j] && graph[u][j] < dist[j])
				dist[j] = graph[u][j];
	}
    int ans = 0;
    for(int i = 0; i < N; i++) ans += dist[i];
    return ans;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	// i <--> j 의 모든 edge를 구하고, MST를 구하면 된다.
	cin >> N >> C;
	for (int i = 0; i < N; i++)
		cin >> point[i].first >> point[i].second;

	// 프림으로 해보자.
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++) {
			int dist = getDist(i, j);
			if (C <= dist) graph[i][j] = graph[j][i] = dist;
			else graph[i][j] = graph[j][i] = INF;
		}
    cout << prim(0) << '\n';
    
	return 0;
	
}