취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16175번 문제인 걸그룹 마스터 준석이이다.
문제는 아래 링크를 확인하자.

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

각 팀과 멤버 사이 관계를 set과 map을 관리하면 문제를 편하게 해결할 수 있다.

각 팀을 입력하면 그 팀의 멤버가 들어있는 집합 set<string>을 반환하는 맵 map<string,set<string>> teamquiz와 각 멤버를 입력하면 그 멤버가 속한 팀을 반환하는 map<string,string> memquiz를 아래와 같이 구현해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;

int N, M;
map<string, string> memquiz;
map<string, set<string>> teamquiz;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	while (N--) {
		string team; cin >> team;
		set<string> members;
		int K; cin >> K;
		while (K--) {
			string mem; cin >> mem;
			members.insert(mem);
			memquiz.insert(make_pair(mem, team));
		}
		teamquiz.insert(make_pair(team, members));
	}

	while (M--) {
		int q; string s; cin >> s >> q;
		if (q) cout << memquiz[s] << '\n';
		else {
			for (auto& x : teamquiz[s]) cout << x << '\n';
		}
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16168번 문제인 퍼레이드이다.
문제는 아래 링크를 확인하자.

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

문제의 조건을 만족하는 경로는 오일러 경로임을 관찰하자.

주어진 그래프가 오일러 경로를 가지기 위한 필요충분조건은 해당 그래프가 연결그래프이며 차수가 홀수인 노드가 2개 이하(2개 또는 0)임과 같다는 점을 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, E;
vector<int> G[3001];
bool visited[3001];

void dfs(int cur) {
	visited[cur] = 1;
	for (auto& node : G[cur]) {
		if (visited[node]) continue;
		dfs(node);
	}
}

int oddcnt;

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

	cin >> N >> E;
	while (E--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	dfs(1);
	for (int i = 1; i <= N; i++) {
		if (G[i].size() & 1) oddcnt++;
		if (!visited[i]) {
			cout << "NO";
			return 0;
		}
	}

	if (oddcnt > 2) cout << "NO";
	else cout << "YES";
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16167번 문제인 A Great Way이다.
문제는 아래 링크를 확인하자.

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

주어진 문제의 상황은 가중치와 방향이 있는 간선으로 이루어진 그래프로 모델링할 수 있다.

또한 주어진 문제를 해결하는 것은 위와 같이 모델링한 그래프 위에서의 1번 노드에서 N번 노드까지의 최소비용 경로의 그 비용과 해당 경로가 가질 수 있는 가장 적은 노드의 개수를 구하는 문제를 해결하는 것과 같아진다.

dijkstra 알고리즘을 이용해 문제를 해결해주자. 이 때 가중치의 기준은 일반적인 dijkstra와 같이 비용으로 하되 두 번째 기준으로 해당 노드까지 (가장 적은 비용으로) 도달하는 데에 필요한 노드의 개수로 삼아 문제를 해결하자.

아래는 제출한 소스코드이다.

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

int N, E;
vector<pair<int,int>> G[101]; // {노드, 거리}
pair<int, int> dist[101];

void dijkstra() {
	dist[1] = { 0,1 };
	priority_queue<pair<pair<int, int>,int>> pq; // {{-거리, -노드수},노드}
	pq.push(make_pair(make_pair(0, -1), 1));

	while (!pq.empty()) {
		int d = -pq.top().first.first, cnt = -pq.top().first.second, cur = pq.top().second; pq.pop();
		if (dist[cur] < make_pair(d, cnt)) continue;
		for (auto& p : G[cur]) {
			int nxt = p.first, dd = d + p.second;
			if (dist[nxt] == make_pair(0, 0) || make_pair(dd, cnt + 1) < dist[nxt]) {
				dist[nxt] = make_pair(dd, cnt + 1);
				pq.push(make_pair(make_pair(-dd, -(cnt + 1)), nxt));
			}
		}
	}
}

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

	cin >> N >> E;
	while (E--) {
		int a, b, c, d, e; cin >> a >> b >> c >> d >> e;
		int t;
		if (e < 10) t = c;
		else t = c + d * (e - 10);
		G[a].emplace_back(make_pair(b, t));
	}

	dijkstra();

	if (dist[N] == make_pair(0, 0)) cout << "It is not a great way.";
	else cout << dist[N].first << ' ' << dist[N].second;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16166번 문제인 서울의 지하철이다.
문제는 아래 링크를 확인하자.

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

BFS를 이용해 문제를 해결하자.

아래와 같이 각 노선이 포함하고 있는 역을 저장하는 벡터와 각 역을 지나는 노선을 저장하는 벡터를 이용하면 구현을 편리하게 할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;

int N;
int idx = 1;
map<ll, int> mp; // {x,i}: x번 역의 새 번호 i
vector<int> L[11]; // [n]: n호선이 포함하는 역 i들
vector<int> S[101]; // [i]: i번 역을 지나는 노선 n들

int dist[101];

void bfs() {
	dist[0] = 1;
	queue<int> que;
	que.push(0);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& n : S[cur]) {
			for (auto& i : L[n]) {
				if (dist[i]) continue;
				dist[i] = dist[cur] + 1;
				que.push(i);
			}
		}
	}
}

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

	mp.insert({0,0});
	cin >> N;
	for (int n = 1; n <= N; n++) {
		int K; cin >> K;
		while (K--) {
			int x; cin >> x;
			if (!mp.count(x)) mp.insert({ x,idx++ });
			x = mp[x];
			L[n].emplace_back(x);
			S[x].emplace_back(n);
		}
	}

	bfs();

	int G; cin >> G;
	if (!mp.count(G)) {
		cout << -1;
		return 0;
	}
	G = mp[G];

	if (G == 0) cout << 0;
	else if (!dist[G]) cout << -1;
	else cout << dist[G] - 2;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16169번 문제인 수행 시간이다.
문제는 아래 링크를 확인하자.

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

계급이 c인 컴퓨터들에 대하여 각각 가능한 가장 빠른 시각에 작업을 시작해 작업을 마치고 모든 계급이 c+1인 컴퓨터들에 정보를 전송하는 것을 시뮬레이션하는 것으로 문제를 해결하자. 즉, 계급단위로 시뮬레이션을 돌려 문제를 해결하자.

이는 아래 구현에서의 C와 같은 벡터의 배열을 이용해 편하게 구현할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<int> C[102];
int T[101];
int val[101];
int ans;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int c, t; cin >> c >> t;
		C[c].emplace_back(i);
		T[i] = t;
	}

	for (int c = 1; c <= N; c++) {
		for(auto& x:C[c]) {
			ans = max(ans, val[x] + T[x]);
			for (auto& y : C[c + 1]) {
				val[y] = max(val[y], val[x] + T[x] + (x - y) * (x - y));
			}
		}
	}

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16173번 문제인 점프왕 쩰리 (Small)이다.
문제는 아래 링크를 확인하자.

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

16174번 문제에서 입력이 작아진 문제이다.

이 문제의 경우 직접 가능한 경로의 경우의 수를 각 칸의 나열의 순열(permutation)을 이용해 탐색해 볼 수도 있겠지만 그 구현보다는 DFS 또는 BFS 등의 그래프 탐색 구현이 더 간단하므로 16174번 문제의 풀이를 참고해 문제를 해결하자.

아래는 제출한 소스코드이다.

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

int N;
int board[3][3];
bool visited[3][3];

void bfs() {
	visited[0][0] = 1;
	queue<pair<int, int>> que;
	que.push(make_pair(0, 0));
	
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		int d = board[r][c];
		if (0 <= r - d && !visited[r - d][c]) {
			visited[r - d][c] = 1;
			que.push(make_pair(r - d, c));
		}
		if (r + d < N && !visited[r + d][c]) {
			visited[r + d][c] = 1;
			que.push(make_pair(r + d, c));
		}
		if (0 <= c - d && !visited[r][c - d]) {
			visited[r][c - d] = 1;
			que.push(make_pair(r, c - d));
		}
		if (c + d < N && !visited[r][c + d]) {
			visited[r][c + d] = 1;
			que.push(make_pair(r, c + d));
		}
	}
}

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

	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) cin >> board[r][c];
	}

	bfs();

	if (visited[N - 1][N - 1]) cout << "HaruHaru";
	else cout << "Hing";
}