2024-02-24

-효율적인 해킹(1325, Baekjoon)

한번의 해킹으로 최대한 많은 컴퓨터를 해킹해야 함으로, 한 컴퓨터에서 BFS탐색을 하여, 몇개의 컴퓨터를 해킹 할 수 있는 지를 알아보는 단방향 그래프탐색 문제였다. 처음에 N범위가 10^4라서, 완전 탐색을 하면, O(n^2)이 걸려 시간초과가 아닐까 싶었지만 문제의 시간제한이 5초로 넉넉하기 때문에 괜찮았다.

<소스코드>

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

int n, m;
vector <int> vec[10010];
int ch[10010], cnt[10010];

void BFS(int x)
{
	int i, j;
	queue <int> q;
	q.push(x);
	ch[x] = 1;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (i = 0; i < vec[now].size(); i++) {
			int now_1 = vec[now][i];
			if (ch[now_1] == 0) {
				ch[now_1] = 1;
				q.push(now_1);
			}
		}
	}
}

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		vec[y].push_back(x);
	}
	int ans = -2e9;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) ch[j] = 0;
		BFS(i);
		for (j = 1; j <= n; j++) if (ch[j] == 1) cnt[i]++;
		if (cnt[i] > ans) ans = cnt[i];
	}
	for (i = 1; i <= n; i++) {
		if (ans == cnt[i]) printf("%d ", i);
	}
	return 0;
}

-숨바꼭질(6118, Baekjoon)

1번 농장에서부터 가장 멀리떨어져있는 농장까지의 최소 거리와 농장의 번호를 구하고, 그 농장과 같은 거리를 갖는 농장의 개수를 구해야한다. 1번에서 시작한다. 즉 시작정점에서부터 다른 정점까지의 최단거리를 구하는 모든 알고리즘을 사용할 수 있으며, 나는 Dijkstra를 이용하여 풀었다.

<소스코드>

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int n, m;
vector <pair<int, int>> vec[20010];
int dis[20020];

void Dijkstra(int x)
{
	int i, j;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, x });
	dis[x] = 0;
	while (!pq.empty()) {
		int now_idx = pq.top().second, now_val = -pq.top().first;
		pq.pop();
		if (dis[now_idx] < now_val) continue;
		for (i = 0; i < vec[now_idx].size(); i++) {
			int idx = vec[now_idx][i].first, val = vec[now_idx][i].second + now_val;
			if (dis[idx] > val) {
				dis[idx] = val;
				pq.push({ -val, idx });
			}
		}
	}
}

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		vec[x].push_back({ y, 1 });
		vec[y].push_back({ x, 1 });
	}
	for (i = 1; i <= n; i++) dis[i] = 2e9;
	Dijkstra(1);
	int ans_idx, ans = -2e9;
	for (i = 1; i <= n; i++) {
		if (dis[i] > ans) {
			ans = dis[i];
			ans_idx = i;
		}
	}
	int cnt = 0;
	for (i = 1; i <= n; i++) if (ans == dis[i]) cnt++;
	printf("%d %d %d", ans_idx, ans, cnt);
	return 0;
}

-이분그래프(1707, Baekjoon)

주어진 그래프가 이분그래프인지 탐색하는 문제로, 직접 인접하는 정점을 다른색으로 칠하며, 다른 인접 정점의 색이 현재 정점의 색과 같다면 바로 NO를 출력하고, 문제없이 모두 칠해진다면 YES를 출력하는 식으로 풀었다.

<소스코드>

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

int k, n, m;
vector <int> vec[20010];
int ans;
int ch[20010];

void BFS(int x)
{
	int i;
	queue<int> q;
	ch[x] = 1;
	q.push(x);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		int check;
		if (ch[now] == 1) check = 2;
		else check = 1;
		for (i = 0; i < vec[now].size(); i++) {
			int nw = vec[now][i];
			if (ch[nw] == 0) {
				ch[nw] = check;
				q.push(nw);
			}
			if (ch[nw] == ch[now]) {
				ans = -1;
				return;
			}
		}
	}
}

int main()
{
	int i, j;
	scanf("%d", &k);
	while (k--) {
		scanf("%d %d", &n, &m);
		for (i = 0; i < m; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			vec[x].push_back(y);
			vec[y].push_back(x);
		}
		for (i = 1; i <= n; i++) if(ch[i] == 0) BFS(i);
		if (ans == -1) printf("NO\n");
		else printf("YES\n");
		for (i = 1; i <= n; i++) {
			ch[i] = 0;
			while (!vec[i].empty()) vec[i].pop_back();
		}
		ans = 0;
	}
	return 0;
}

-구슬 찾기(2617, Baekjoon)

예전에 풀었던 KOI수학 문제와 비슷해서, 풀이가 금방 떠올랐다. 주어진 대소관계에서 x가 y보다 클 때, 이를 x -> y 와 y -> x로 각각 저장하여, 그래프를 만든다. 그 후, 상위 노드의 수와 하위 노드의 수를 각각 BFS탐색을 통해 구하여, 가운데 오지못하는 경우((n+1)/2보다 큰 경우) ,cnt를 증가시켜 풀었다.

<소스코드>

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

int n, m;
vector <int> vec1[100], vec2[100];
int dis1[100], dis2[100];
int ch[100];

void BFS1(int x)
{
	int i;
	queue<int> q;
	q.push(x);
	ch[x] = 1;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (auto i : vec1[now]) {
			if (ch[i] == 0) {
				ch[i] = 1;
				q.push(i);
			}
		}
	}
}

void BFS2(int x)
{
	int i;
	queue<int> q;
	q.push(x);
	ch[x] = 1;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (auto i : vec2[now]) {
			if (ch[i] == 0) {
				ch[i] = 1;
				q.push(i);
			}
		}
	}
}

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		vec1[x].push_back(y);
		vec2[y].push_back(x);
	}
	for (i = 1; i <= n; i++) {
		BFS1(i);
		int cnt = 0;
		for (j = 1; j <= n; j++) if (i != j && ch[j] == 1) cnt++;
		dis1[i] = cnt;
		for (j = 1; j <= n; j++) ch[j] = 0;
	}
	for (i = 1; i <= n; i++) {
		BFS2(i);
		int cnt = 0;
		for (j = 1; j <= n; j++) if (i != j && ch[j] == 1) cnt++;
		dis2[i] = cnt;
		for (j = 1; j <= n; j++) ch[j] = 0;
	}
	int ans = 0;
	int mid = (n + 1) / 2;
	for (i = 1; i <= n; i++) {
		if (mid <= dis1[i] || mid <= dis2[i]) ans++;
	}
	printf("%d", ans);
	return 0;
}

-나누기(21757, Baekjoon) 

굉장이 해매다가 에디토리얼을 보고 풀었다. 생각보다 쉬운 문제라 반성을 좀 했었다.

누적합을 이용하여 푸는 문제였다. 문제를 읽어보면 나올 수 있는 경우는 총 3가지 경우가 있다.

1. 전체구간의 누적합이 4로나누어 떨어지지 않는 경우

2. 전체구간의 누적합이 0인경우

3. 전체구간의 누적합이4로 나누어 떨어지는 경우이다.

1번경우는 각부분의 합이 똑같이 4개의 구간으로 나누는 경우가 있을 수 없음으로, 0이 답이다.

2번 경우는 누적합이 0이 되는 구간의 총 수를 구하여, 이를 3가지 그룹으로 나누는 경우의 수를 수식으로 표현하여 구해준다.

3번경우는 전체구간의 누적합을 4로나눈이 하나의 구간이 되어야함으로, n번 탐색을 해보며, 현재의 누적합의 값을 (전체구간 누적합)/4로 나누어, 몇번째 구간인지를 구한 후, 이가 나누어떨어지며, 1과 4 사이의 수라면, 그전 구간의 값을 더하여 준다.

이렇게 3경우를 모두 처리하여 답을 구하였다.

#include <stdio.h>

long long n, ans;
long long arr[100010], sum[100010];
long long dp[5], dv;

int main()
{
	long long i, j;
	scanf("%lld", &n);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &arr[i]);
		sum[i] = sum[i - 1] + arr[i];
	}
	dp[0] = 1;
	dv = sum[n] / 4;
	if (sum[n] == 0) {
		long long cnt = 0;
		for (i = 1; i <= n; i++) if(sum[i] == 0) cnt++;
		ans = (cnt - 1) * (cnt - 2) * (cnt - 3) / 6;
	}
	else if (sum[n] % 4 != 0) ans = 0;
	else {
		for (i = 1; i <= n; i++) {
			long long res = sum[i] / dv;
			if (sum[i] % dv != 0 || res < 1 || 4 < res) continue;
			dp[res] += dp[res - 1];
		}
		ans = dp[3];
	}
	printf("%lld", ans);
	return 0;
}