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

1. 문제설명

단방향 그래프 관계가 주어지고

그래프에서 간선의 방향을 수정했을 때

위상정렬을 수행하면 단 하나의 경우의 수만 나오는지 확인하는 문제다.

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

우선 위상정렬을 수행하는데 확인해야 할 게 두가지 있다.

첫 번째는

단 하나의 경우의 수만 등장하는지 ==

확실한 순위를 찾을 수 있는지 확인해야한다.

이를 확인하려면 위상정렬을 하면서 큐의 size를 확인해야 한다.

만약 하나의 노드에서 여러 노드로 퍼질 수 있다면

큐의 사이즈가 2를 넘게 되고 이때는 위상정렬의 가짓 수가 여러개가 되어서 확실한 순위를 찾을 수 없다.

두번째는 

사이클이 존재하다면 IMPOSSIBLE을 출력해야한다.

사이클이 존재하면 위상정렬이 불가능하고,

그 경우에 위상정렬 과정에서 degree(차수) 가 0이 되지 않는 노드가 생기기 때문에

모든 노드를 탐색하지 못한다.

3. 문제풀이코드 C++

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

bool adj[501][501];
int degree[501];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    for (int T = 0; T < t; T++) {

        memset(adj, 0, sizeof(adj));
        memset(degree, 0, sizeof(degree));
        int n;
        cin >> n;

        vector<int> pre;
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            pre.push_back(tmp);
        }

		for (int i = 0; i < pre.size(); i++) {
            for (int j = i + 1; j < pre.size(); j++) {
                adj[pre[i]][pre[j]] = 1;
                degree[pre[j]]++;
            }
        }

        int m;
        cin >> m;


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

            if (adj[a][b] == 1) {
                adj[a][b] = 0;
                degree[b]--;
                adj[b][a] = 1;
                degree[a]++;
            }
            else {
                degree[a]--;
                adj[b][a] = 0;
                adj[a][b] = 1;
                degree[b]++;
            }
        }

        
        queue<int> Q;

        for (int i = 1; i <= n; i++) {
            if (degree[i] == 0) {
                Q.push(i);
            }
        }

        vector<int> ans;

        bool cantKnow = false;

        while (!Q.empty()) {

            if (Q.size() >= 2) {
                cantKnow = true;
                break;
            }

            int x = Q.front(); Q.pop();
            ans.push_back(x);

            for (int i = 1; i <= n; i++) {
                if (adj[x][i] == 1) {
                    int nx = i;

                    if (--degree[nx] == 0) {
                        Q.push(nx);
                    }

                }
            }
        }

        if (cantKnow) {
            cout << "?\n";
            continue;
        }


        if (ans.size()!=n) {
            cout << "IMPOSSIBLE\n";
            continue;
        }
        else {
			for (auto x : ans) {
				cout << x << ' ';
			}
			cout << '\n';
        }


    }
  
    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

int n, m;

int arr[1001][1001];
vector<pair<int, int> > wall;
bool ch[1001][1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int num[1001][1001];
int marked[1001*1001]; // cnt[mark] = 개수 


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n >> m;
    for (int i = 0; i < n; i++) {

        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            arr[i][j] = s[j]-'0';
            if (arr[i][j]) wall.push_back({ i,j });
        }
    }

    int mark = 1;
	queue<pair<int, int> > Q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            
            if (arr[i][j] == 0 && num[i][j] == 0) {
				int cnt = 1;
                Q.push({ i,j });
                num[i][j] = mark;
                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 || num[nx][ny] || arr[nx][ny]) continue;
                        Q.push({ nx,ny });
                        cnt++;
                        num[nx][ny] = mark;
                    }
                }
				marked[mark] = cnt;
				mark++;
            }
        }
    }

    for (int i = 0; i < wall.size(); i++) {
        int x = wall[i].first;
        int y = wall[i].second;

        int wall_cnt = 1;
        set<int> s;

        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;
            s.insert(num[nx][ny]);
        }

        for (auto k : s) {
            wall_cnt += marked[k];
        }
        arr[x][y] = (wall_cnt % 10);
    }




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

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

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


vector<char> elec;
vector<pair<int, int> > graph[1001];

struct Edge {
	int x, val;
	bool operator<(const Edge& b) const {
		return val > b.val;
	}
};

bool vis[1001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, k;
	cin >> n >> m >> k;

	priority_queue<Edge> Q;


	for (int i = 0; i < k; i++) {
		int c;
		cin >> c;
		Q.push({ c,0 });
	}

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

	int ans = 0;

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

		if (vis[x] == 0) {
			vis[x] = 1;
			ans += val;

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

				if (vis[nx] == 0) {
					Q.push({ nx,nd });
				}
			}
		}
	}

	cout << ans << '\n';
	

	return 0;
}

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

1.문제설명

1번 노드에서 출발하여 다른 모든 노드까지의 K번째 최단 거리를 찾는 문제이다.

일반적으로

한 노드에서 다른 모든 노드까지의 최단 거리를 구할 때 다익스트라 알고리즘을 이용한다.

이 문제도 다익스트라 알고리즘을 응용하면 K번째 최단거리를 구할 수 있다.

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

이 문제에서 가장 헷갈리는 점은 

기존 최단거리를 구하는 다익스트라 알고리즘과 다르게

방문한 노드를 재방문해도 된다는 점이다.

방문한 노드를 재방문해도 되도록 코드를 구성하면

계속 무한루프에 빠지지 않을까?

이를 해결하기 위해 

방문 여부 대신 다른 조건을 추가해주어야 한다.

그림에 잘 보면 2->3->5->2가 계속 무한으로 순환할 수 있다.

노드를 방문하는 우선순위큐와 다르게

특정 노드까지 거리를 저장하는 우선순위큐 배열을 따로 두어서

K번째 최단 거리까지 구했다면 더 이상 순환하지 않도록 코드를 구현해야 한다.

3.문제풀이코드 C++

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

int n, m, k;
struct Edge {
	int x;
	long long val;
	bool operator<(const Edge& b) const {
		return val > b.val;
	}
};

vector<pair<int, int> > graph[1001];
priority_queue<int> Node[1001];
priority_queue<Edge> Q;

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

	cin >> n >> m >> k;

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

	Node[1].push(0);
	Q.push({ 1,0 });

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

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

			if (Node[nx].size() < k) {
				Node[nx].push(nd);
				Q.push({ nx,nd });
			}
			else {
				if (Node[nx].top() > nd) {
					Node[nx].pop();
					Node[nx].push(nd);
					Q.push({ nx,nd });
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (Node[i].size() < k) {
			cout << -1 << '\n';
		}
		else {
			cout << Node[i].top() << '\n';
		}
	}


	return 0;
}

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

1.문제설명

INPUT

5
0 6 15 2 6
6 0 9 8 12
15 9 0 16 18
2 8 16 0 4
6 12 18 4 0

OUTPUT

55

문제에서 N개의 노드가 있을 때

노드에서 노드로 가는 모든 최단 거리를 INPUT으로 준다.

주어진 노드간 최단 거리를 유지하면서 간선의 개수를 최소로 할 때 

간선의 거리의 합을 구해야 한다.

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

주어진 인풋을 dist배열에 넣고

플로이드 워셜을 한번 실행했을 때

dist[i][k] + dist[k][j]) == dist[i][j]

이런 상황이 있으면 간선을 최소로 하기위해

dist[i][j] 의 간선을 사용하지 않고

dist[i][k] 와 dist[k][j]의 간선만 사용하면 된다.

맨 처음엔 문제에서 주어진 인풋의 간선을 모두 사용하는 걸 전제로 하고

위와 같은 간선이 있으면 i - j 를 이어주는 간선을 없애주면

최소 간선을 구해낼 수 있다.

for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j || j == k || i == k) continue;
				if ((dist[i][k] + dist[k][j]) == dist[i][j]) {
					arr[i][j] = INF;
				}
				else if (dist[i][k] + dist[k][j] < dist[i][j]) {
					cout << -1 << '\n';
					return 0;
				}
			}
		}
	}

3. 문제풀이코드 C++

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


const int INF = 0x3f3f3f3f;

int n, arr[21][21];

int dist[21][21];
bool ch[21][21];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			dist[i][j] = min(dist[i][j], arr[i][j]);
		}
	}

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j || j == k || i == k) continue;
				if ((dist[i][k] + dist[k][j]) == dist[i][j]) {
					arr[i][j] = INF;
				}
				else if (dist[i][k] + dist[k][j] < dist[i][j]) {
					cout << -1 << '\n';
					return 0;
				}
			}
		}
	}

	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] < INF) sum += arr[i][j];
		}
	}

	cout << sum / 2 << '\n';



	return 0;
}

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

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

vector<int> gun;


bool distance(int x, int y, int L) {

	bool ans = false;
	if (y > L) return false;

	int s = 0;
	int e = gun.size() - 1;

	while (s <= e) {

		int mid = (s + e) / 2;

		if (abs(gun[mid] - x) + y <=L) {
			ans = true;
			break;
		}
		else if (gun[mid] > x) {
			e = mid - 1;
		}
		else {
			s = mid + 1;
		}
	}


	return ans;
}


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

	int m, n, l;
	cin >> m >> n >> l;
	

	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp;
		gun.push_back(tmp);
	}

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

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		if (distance(x, y ,l)) cnt++;
	}

	cout << cnt << '\n';


	

	return 0;
}

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/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;
}