[BOJ 24617 // C++] Redistributing Gifts

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

 

이번에 볼 문제는 백준 24617번 문제인 Redistributing Gifts이다.
문제는 아래 링크를 확인하자.

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

24617번: Redistributing Gifts

각 소들끼리 선물을 서로 교환해 처음 자신이 들고 있던 선물과 같거나 더 마음에 드는 선물을 들려고 할 때, 각 소마다 가지게 될 수 있는 가장 좋은 선물이 각자 무엇인지를 찾는 문제이다.

 

선물 i를 가지고 있는 소의 자신이 더 갖고싶은 각 선물 j에 대하여 dist[i][j] = 1로 하는 방향그래프를 만들었을 때, 이 그래프에 i에서 j로 향하는 에지를 포함하는 사이클이 존재한다면 해당 사이클의 에지의 반대방향으로 각자 선물을 넘겨 주는 것으로 선물 i를 가질 수 있게 된다.

 

Floyd-Warshall 알고리즘을 이용하여 모든 (i,j) 순서쌍에 대해 이동 가능 여부를 전처리한 후(거리가 구해진다면 이동 가능), 이를 이용하여 사이클 판정을 빠르게 하며 각 소가 가질 수 있는 가장 원하는 선물을 빠르게 구해 문제를 해결하자.

 

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

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

int dist[501][501];
int priority[501][501];

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

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

	int N; cin >> N;
	for (int r = 1; r <= N; r++) {
		bool chk = 1;
		for (int i = 1; i <= N; i++) {
			int x; cin >> x;
			if (x == r) chk = 0;
			if (chk) {
				dist[r][x] = 1;
				priority[r][x] = i;
			}
		}
	}

	for (int k = 1; k <= N; k++) {
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				dist[r][c] = min(dist[r][c], dist[r][k] + dist[k][c]);
			}
		}
	}

	for (int r = 1; r <= N; r++) {
		int ans = r, prior = priority[r][r];
		for (int c = 1; c <= N; c++) {
			if (dist[r][c] == 1 && dist[c][r] < 0x3f3f3f3f && priority[r][c] < prior) ans = c, prior = priority[r][c];
		}
		cout << ans << '\n';
	}
}