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

1.문제설명

문제가 꽤 복잡하다.

단순하게 정리하면

시작점과 꼭 경유해야하는 간선이 주어졌을 때 해당하는 노드가

문제에서 원하는 도착점이 될 수 있는지

판단해야한다.

2.접근방법[알고리즘]

https://www.acmicpc.net/board/view/47684

도착점 후보가 진짜로 도착점인지 확인하려면

시작점으로부터 경유지를 경유하고 도착점 후보에 도착한 거리와

시작점으로부터 도착점 후보까지의 최단 거리가 같아야한다.

이를 바탕으로 최단거리에 도달 했을 때 g와 h의 간선을 지났다면

해당 도착점후보가 도착점이 될 수 있음을 알 수 있다.

그래서 g-h 간선을 지났는지 여부를 따로 저장해주면서 확인하면 이 문제를 해결 할 수 있다.

다만 핵심은 priority_queue를 이용할 때

거리와 노드가 동일하다면 g-h간선이 지난 여부가 true인 상태가

우선으로 pop 되도록 설계해야 한다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
	int x, d;
	bool ispassing;

	bool operator<(const Node& b) const {
		if (x == b.x && d == b.d) {
			return ispassing < b.ispassing;
		}
		return d > b.d;
	}

};


bool dijkstra(vector<pair<int, int> >* v, int st, int en, int g, int h) {
	bool passed = false;

	int dist[2001];
	memset(dist, 0x3f, sizeof(dist));

	priority_queue<Node> Q;
	Q.push({ st,0,0 });

	while (!Q.empty()) {
		int x = Q.top().x;
		int d = Q.top().d;
		bool p = Q.top().ispassing;

		Q.pop();

		if (dist[x] <= d) continue;
		dist[x] = d;

		if (x == en) {
			if (p) {
				passed = true;
			}

			break;
		}

		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i].first;
			int nd = d + v[x][i].second;

			if (dist[nx] > nd) {
				if (p) {
					Q.push({ nx,nd,p });
				}
				else {
					if ((x == g && nx == h) || (x == h && nx == g)) {
						Q.push({ nx,nd,1 });
					}
					else {
						Q.push({ nx,nd,0 });
					}
				}
			}

		}

	}
	return passed;
}

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

	int tt;
	cin >> tt;

	for (int T = 0; T < tt; T++) {

		vector<pair<int, int> > v[2001];

		int n, m, t;
		int s, g, h;
		cin >> n >> m >> t;
		cin >> s >> g >> h;

		for (int i = 0; i < m; i++) {
			int a, b, d;
			cin >> a >> b >> d;

			v[a].push_back({ b,d });
			v[b].push_back({ a,d });
		}

		vector<int> ans;
		for (int i = 0; i < t; i++) {
			int x;
			cin >> x;


			if (dijkstra(v, s, x, g, h)) {
				ans.push_back(x);
			}

		}

		sort(ans.begin(), ans.end());

		for (int i = 0; i < ans.size(); i++) {
			cout << ans[i] << ' ';
		}

		cout << '\n';

	}


	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int n, m, st, en;

pair<int, int> dist[1001]; //거리 , 이전노드 저장 

vector<pair<int, int> > v[1001];

struct Node {
	int x, ex ,d;
	bool operator<(const Node& b)const {
		return d > b.d;
	}
};

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


	memset(dist, 0x3f, sizeof(dist));

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b, c });
	}

	cin >> st >> en;
	priority_queue<Node> Q;
	Q.push({ st,-1,0 });

	vector<int> ans;


	while (!Q.empty()) {
		int x = Q.top().x;
		int ex = Q.top().ex;
		int d = Q.top().d;
		Q.pop();

		if (dist[x].first <= d) continue;

		dist[x].first = d;
		dist[x].second = ex;


		if (x == en) {
			int a = en;

			while (a != -1) {
				ans.push_back(a);
				a = dist[a].second;
			}

			cout << d << '\n';
			cout << ans.size() << '\n';

			for (int i = ans.size() - 1; i >= 0; i--) {
				cout << ans[i] << ' ';
			}
			return 0;
		}


		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i].first;
			int nd = d + v[x][i].second;

			if (dist[nx].first > nd) {
				Q.push({ nx,x,nd });
			}
		}
	}



	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;


int res[1001];

struct Node {
	int x, dist;

	bool operator<(const Node& b) const{
		return dist > b.dist;
	}
};

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

	memset(res, 0x3f, sizeof(res));

	int n, m, st, end;
	vector<Node> map[1001];

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		map[a].push_back({ b,c });
	}
	cin >> st >> end;

	priority_queue<Node> Q;

	Q.push({ st,0 });
	res[st] = 0;

	while (!Q.empty()) {
		int x = Q.top().x;
		int d = Q.top().dist;
		Q.pop();

		
		if (res[x] < d) continue;
		
		res[x] = d;
		if (x == end) {
			cout << d << '\n';
			return 0;
		}

		for (int i = 0; i < map[x].size(); i++) {
			int nx = map[x][i].x;
			int nd = map[x][i].dist;

			if (res[nx] > nd + d) {
				Q.push({ nx,nd + d });
			}

		}
	}

	return 0;
}

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

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

#include <bits/stdc++.h>
using namespace std;

struct Ball {
	int idx, color, size;

	bool operator<(const Ball& b) const {
		if (size == b.size) return idx < b.idx;
		else return size < b.size;
	}
};

int color[200001], sum;
int ans[200001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;

	cin >> n;
	vector<Ball> v;
	v.push_back({ 0,0,0 });

	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ i,a,b });
	}
	sort(v.begin(), v.end());

	for (int i = 1, j = 1; i <= n; i++) {
		while (v[i].size > v[j].size) {
			sum += v[j].size;
			color[v[j].color] += v[j].size;
			j++;
		}
		ans[v[i].idx] = sum - color[v[i].color];
	}



	for (int i = 1; i <= n; i++) {
		cout << ans[i] << '\n';
	}

	return 0;
}

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

접근방법[알고리즘]

2차원 배열로 분수 형태를 나타낼 수 있다.

분수를 기약분수로 나타내기 위해 최대공약수를 이용해야 한다.

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int GCD(int a, int b) {
	if (a < b) swap(a, b);
	if (a % b == 0) {
		return b;
	}
	else {
		return GCD(b, a % b);
	}
}

bool ch[2001][2001];

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


	int a, b;
	cin >> a >> b;
	int ans = 1;

	for (int i = a; i <= b; i++) {
		for (int j = 1; j < i; j++) {
			int mod = GCD(i, j);
			int a = j / mod;
			int b = i / mod;
			if (ch[a][b] == 0) {
				ans++;
				ch[a][b] = 1;
			}
		}
	}


	cout << ans <<'\n';

	return 0;
}

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

접근방법[알고리즘]

1. 빙산이 몇개의 덩어리로 이루어져있는지 BFS를 이용해 개수를 센다.

2. 빙산의 개수가 2개이상이거나 0이 아니면 빙산을 한차례 녹인다.

3. 1과 2를 반복한다.

주의할 점

빙산이 녹아 없어지는 경우 바로 0으로 만들어버리면
다음 빙산에 영향을 줘서 틀린다.
빙산이 0이 되는 경우는 따로 저장해뒀다가 큐를 한바퀴 다 돈다음
적용 해주어야 한다.

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[301][301] ,t;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int Count() {
	int check[301][301];
	int ans = 1;
	memset(check, 0, sizeof(check));
	queue<pair<int, int> > Q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] > 0 && check[i][j]==0) {
				check[i][j] = ans;
				Q.push({ i,j });

				while (!Q.empty()) {
					int x = Q.front().first;
					int y = Q.front().second;
					Q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];
						if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] == 0) continue;
						if (check[nx][ny] == 0) {
							check[nx][ny] = ans;
							Q.push({ nx,ny });
						}
					}
				}
				ans++;
			}
		}
	}
	return ans - 1;
}


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

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


	while (1) {
		int area = Count();
		if (area >= 2) {
			cout << t << '\n';
			return 0;
		}
		else if (area == 0) {
			cout << 0 << '\n';
			return 0;
		}

		int s = Q.size();
		//빙산이 녹아 없어지는 경우 바로 0으로 만들어버리면
		//다음 빙산에 영향을 줘서 틀린다.
		//빙산이 0이 되는 경우는 따로 저장해뒀다가 큐를 한바퀴 다 돈다음
		//적용 해주어야 한다.

		vector<pair<int, int> > melt;
		for (int i = 0; i < s; i++) {
			int x = Q.front().first;
			int y = Q.front().second;
			Q.pop();

			int cnt = 0;
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny]>0) continue;
				cnt++;
			}

			if (cnt >= arr[x][y]) {
				melt.push_back({ x,y });
			}
			else {
				arr[x][y] -= cnt;
				Q.push({ x,y });
			}
		}
		for (int i = 0; i < melt.size(); i++) {
			arr[melt[i].first][melt[i].second] = 0;
		}

		t++;
	}

	return 0;
}

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

1.문제설명

두 로봇이 통신하기 위해 이동해야하는 최단 거리를 구해야한다.

두 로봇은 같은 노드에 있거나 서로 연결된 노드에 위치하면 통신할 수 있다.

2.접근방법[알고리즘]

처음에는 문제에 주어진 대로 로봇 두대를 놓고 한 로봇 씩 이동시키면서 

통신할 수 있는지 확인하고 그 때 이동한 거리를 계속 갱신해주면서 답을 구했는데

이러면 n이 10만이기 때문에 시간초과로 틀렸다.

문제의 조건에서

N개의 노드와 N-1의 간선이 있기 때문에

이미 지나온 노드를 재방문 할 수 없을 때

출발 지점에서 도착 지점까지 가는 경로는 무조건 하나만 나오고, 그게 최단 경로가 된다.

이 문제를 해결하려면

1. 두 로봇의 시작점 사이의 거리를 구한다.

2. 시작점을 이어주는 통로 중 길이가 가장 긴 간선을 구한다.

3. 답 = 시작점 사이 거리 - 가장 긴 간선 거리 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, s1, s2;
vector<pair<int, int> > m[100001];

bool ch[100001];
bool flag = false;

void DFS(int x, int sum, int max_dist) {
	if (flag) return;
	if (x == s2) {
		cout << sum - max_dist << '\n';
		flag = true;
		return;
	}

	for (int i = 0; i < m[x].size(); i++) {
		int nx = m[x][i].first;
		int nd = m[x][i].second;
		if (ch[nx] == 0) {
			ch[nx] = 1;
			DFS(nx, sum + nd, max(nd,max_dist));
		}
	}

	return;
}

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

	cin >> n >> s1 >> s2;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		m[a].push_back({ b,c });
		m[b].push_back({ a,c });
	}
	ch[s1] = 1;
	DFS(s1, 0, 0);

	return 0;
}

DFS를 돌면서 다른 로봇의 시작점을 만나면 바로 종료해주면 된다.

해당 정점까지 가는 다른 방법이 존재하지 않기 때문이다.

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

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[103][103], ans;
queue<pair<int, int> > Q;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };


// 1. 공기 구역 BFS
// 2. 공기와 접한 치즈 사라짐
// 1, 2 반복 
bool air[103][103];
queue<pair<int, int> > airQ;


void air_spread() {
	while (!airQ.empty()) {
		int x = airQ.front().first;
		int y = airQ.front().second;
		airQ.pop();

		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 || air[nx][ny] == 1) continue;
			if (arr[nx][ny] == 0) {
				airQ.push({ nx,ny });
				air[nx][ny] = 1;
			}
		}
	}
}


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

	cin >> n >> m;
	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({ i,j });
			}
		}
	}

	// 맨 처음 공기인 부분 
	for (int i = 0; i < n; i++) {
		air[i][0] = 1;
		airQ.push({ i,0 });
		air[i][m - 1] = 1;
		airQ.push({ i,m - 1 });
	}

	for (int i = 0; i < m; i++) {
		air[0][i] = 1;
		airQ.push({ 0,i });
		air[n-1][i] = 1;
		airQ.push({ n-1, i});
	}


	int t = Q.size();
	while (!Q.empty()) {
		air_spread();
		t = Q.size();
		vector<pair<int, int> > melt;

		for (int q = 0; q < t; q++) {
			int x = Q.front().first;
			int y = Q.front().second;
			Q.pop();

			bool has_hole = false;
			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) continue;
				if (air[nx][ny] == 1) {
					melt.push_back({ x,y });
					has_hole = true;
					break;
				}
			}
			if (!has_hole) Q.push({ x,y });
		}

		for (int i = 0; i < melt.size(); i++) {
			arr[melt[i].first][melt[i].second] = 0;
			air[melt[i].first][melt[i].second] = 1;
			airQ.push({ melt[i].first, melt[i].second });
		}
		ans++;
	}

	cout << ans << '\n';
	cout << t << '\n';
	return 0;
}