2024-03-16

-아기 상어(16236, 백준)

 BFS를 이용한 구현 문제이다. n범위가 크지 않음으로, 물고기를 잡아먹을 때 마다 층을 나누어 구해주었다. 구현이 힘든것이지 문제의 아이디어는 그렇게 높지 않다. 자잘한 실수가 나오기 쉬운 문제라고 생각한다.

<소스 코드>

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

using namespace std;

int dx[5] = { -1, 0, 1, 0 };
int dy[5] = { 0, -1, 0, 1 };
int dis[25][25][410], ch[25][25][410];
int map[25][25], now_size[410];
int n, cnt;
int ansdis = 0;

struct dat {
	int x, y, cnt;
};

queue <dat> q;

void BFS()
{
	int i, j;
	while (!q.empty()) {
		int n_x = q.front().x, n_y = q.front().y, ncnt = q.front().cnt;
		q.pop();
		for (i = 0; i < 4; i++) {
			int nx = n_x + dx[i], ny = n_y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (!ch[nx][ny][ncnt] && map[nx][ny] != 0 && map[nx][ny] < now_size[cnt]) {
				ch[nx][ny][ncnt] = -1;
				dis[nx][ny][ncnt] = dis[n_x][n_y][ncnt] + 1;
				q.push({ nx, ny, ncnt });
			}
			else if (!ch[nx][ny][ncnt] && map[nx][ny] <= now_size[cnt]) {
				ch[nx][ny][ncnt] = 1;
				dis[nx][ny][ncnt] = dis[n_x][n_y][ncnt] + 1;
				q.push({ nx, ny, ncnt });
			}
		}
	}
}

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			for (int k = 0; k <= 400; k++) {
				dis[i][j][k] = 2e9;
			}
		}
	}
	int ct = 0, sz = 2;
	now_size[0] = 2;
	for (i = 1; i <= n * n; i++) {
		ct++;
		if (ct == sz) sz++, ct = 0;
		now_size[i] = sz;
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 9) dis[i][j][0] = 0, ch[i][j][0] = 1, map[i][j] = 0, q.push({i, j, 0});
		}
	}
	while (1) {
		BFS();
		int mindis = 2e9;
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				if (ch[i][j][cnt] == -1) mindis = min(mindis, dis[i][j][cnt]);
			}
		}
		int check = 0;
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				if (ch[i][j][cnt] == -1 && dis[i][j][cnt] == mindis) {
					ansdis = dis[i][j][cnt];
					dis[i][j][cnt + 1] = dis[i][j][cnt];
					ch[i][j][cnt + 1] = 1;
					map[i][j] = 0;
					q.push({ i, j, cnt + 1 });
					check = 1;
					break;
				}
			}
			if (check == 1) break;
		}
		if (q.empty()) break;
		cnt++;
	}
/*	for (i = 0; i <= cnt; i++) {
		printf("\n\n\n\n<물고기를 %d번 잡아먹음>\n", i);
		for (j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				if (dis[j][k][i] >= 2e9) printf("INF ");
				else printf("%d ", ch[j][k][i]);
			}
			printf("\n");
		}
	}*/
	printf("%d", ansdis);
	return 0;
}

-장난감 조립(2637, 백준)

 위상정렬 문제이다. 간단하게 처음에 진입차수가 없는 부품은 기본 부품이기 때문에, 이들만 자신의 부품수 1로 초기화를 해둔 뒤, 진입차수를 감소시킬 때마다 전 부품에 필요한 기본부품의 수를 더해주며 풀었다.

<소스 코드>

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

using namespace std;

int n, m;
int ans[110][110];
int ent[110];
vector <pair<int, int>> vec[110];

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		vec[y].push_back({ x, z });
		ent[x]++;
	}
	queue <int> q;
	for (i = 1; i <= n; i++) {
		if (ent[i] == 0) {
			q.push(i);
			ans[i][i] = 1;
		}
	}
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (i = 0; i < vec[now].size(); i++) {
			int nw = vec[now][i].first;
			ent[nw]--;
			for (j = 1; j <= n; j++) ans[nw][j] += (ans[now][j] * vec[now][i].second);
			if (ent[nw] == 0) {
				q.push(nw);
			}
		}
	}
	for (i = 1; i <= n; i++) if(ans[n][i] > 0) printf("%d %d\n", i, ans[n][i]);
	return 0;
}

 

-외판원 순회(2098, 백준)

 비트필드를 이용한 DP의 기본 문제이다. TSP 알고리즘을 구현하는 문제이다. 비트마스킹을 이용하여, 현재까지 방문한 도시를 저장하는식으로 2차원 DP를 잡으면 된다. dp[i][j] = 현재 도시 i이고 현재까지 방문한 도시 리스트가 j일 때 남은 모든 도시를 경유하는데 드는 최소 비용

<소스 코드>

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

using namespace std;

int n;
int arr[20][20];
int dp[1 << 20][20];

int TSP(int vis, int c)
{
	int i, j;
	vis |= (1 << c);
	if (vis == (1 << n) - 1) {
		if (arr[c][0] > 0) {
			return arr[c][0];
		}
		else return 2e9;
	}
	if (dp[vis][c] > 0) return dp[vis][c];
	dp[vis][c] = 2e9;
	for (i = 0; i < n; i++) {
		if (i != c && (vis & (1 << i)) == 0 && arr[c][i] > 0) {
			int res = TSP(vis, i) + arr[c][i];
			if (dp[vis][c] > res) dp[vis][c] = res;
		}
	}
	return dp[vis][c];
}

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	int ans = TSP(0, 0);
	if (ans == 2e9) printf("-1\n");
	else printf("%d", ans);
	return 0;
}

-할 일 정하기 1(1311, 백준)

 비트필드를 이용한 DP 기본문제이다. 비트마스킹을 이용하여 현재 할당된 일들을 저장해 준다. 일이 비어있다면 현재 탐색중인 사람을 비어있는 일에 할당시키는 식으로 풀었다. dp[i][j] = i번째 사람이 할 일을 탐색중이고, 현재까지 할당된 일의 리스트가 j일때의 최소값.

<소스 코드>

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

using namespace std;
int n;
int arr[25][25];
int dp[21][1 << 21];

int dpinit(int c, int vis)
{
	int i, j;
	if (vis == (1 << n) - 1) return 0;
	if (dp[c][vis] != -2e9) return dp[c][vis];
	dp[c][vis] = 2e9;
	for (i = 0; i < n; i++) {
		if ((vis & (1 << i))) continue;
		dp[c][vis] = min(dp[c][vis], dpinit(c + 1, vis | (1 << i)) + arr[c][i]);
	}
	return dp[c][vis];
}

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	for (i = 0; i < 20; i++) {
		for (j = 0; j < 1 << 20; j++) {
			dp[i][j] = -2e9;
		}
	}
	printf("%d", dpinit(0, 0));
	return 0;
}

-도로포장(1162, 백준)

 벽부수고 이동하기를 풀어봤다면, 아이디어가 금방 떠오른다. 벽부수고 이동하기 + 다익으로 풀린다. dis[i][j] = i번째 도시까지 j번 도로를 포장하고 갈때 걸리는 최소 시간.

<소스 코드>

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

using namespace std;

long long n, m, k;
long long dis[10010][25];
vector <pair<long long, long long>> vec[10010];

struct dat {
	long long x, y, brk;
};

bool operator <(const dat& a, const dat& b) {
	return a.x > b.x;
}

void Dijkstra(long long s)
{
	long long i, j;
	priority_queue <dat> pq;
	dis[s][0] = 0;
	pq.push({ 0, s, 0 });
	while (!pq.empty()) {
		long long nidx = pq.top().y, nval = pq.top().x, nbrk = pq.top().brk;
		pq.pop();
		if (dis[nidx][nbrk] < nval) continue;
		for (i = 0; i < vec[nidx].size(); i++) {
			long long idx = vec[nidx][i].first, val = vec[nidx][i].second + nval;
			if (nbrk + 1 <= k && dis[idx][nbrk + 1] > nval) {
				dis[idx][nbrk + 1] = nval;
				pq.push({ nval, idx, nbrk + 1 });
			}
			if (dis[idx][nbrk] > val) {
				dis[idx][nbrk] = val;
				pq.push({ val, idx, nbrk });
			}
		}
	}
}

int main()
{
	long long i, j;
	scanf("%lld %lld %lld", &n, &m, &k);
	for (i = 0; i < m; i++) {
		long long x, y, z;
		scanf("%lld %lld %lld", &x, &y, &z);
		vec[x].push_back({ y, z });
		vec[y].push_back({ x, z });
	}
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= k; j++) {
			dis[i][j] = 2e19;
		}
	}
	Dijkstra(1);
	long long ans = 2e19;
	for (i = 0; i <= k; i++) ans = min(ans, dis[n][i]);
	printf("%lld", ans);
	return 0;
}