글 읽기 - 이거는 왜 4점일까요? (스포조심!)

paparoni 2년 전 0

좌표의 개념(i, j)를 하나의 노드로 표현한 차이 밖에 없고 나머지 로직은 같습니다.

그런데 4점을 맞는 이유가 뭘까요??...

제가 놓치는 부분이 있을까요?

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

int T, R, C;
const int MAX = 501;
int parent[MAX];

vector<pair<int, pair<int, int> > > edges;

int find(int x)
{
	if (x == parent[x]) return x;
	return parent[x] = find(parent[x]);
}

void merge(int a, int b)
{
	a = find(a);
	b = find(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

void kruskal()
{
	for (int i = 1; i <= R * C; i++) parent[i] = i;
	sort(edges.begin(), edges.end());
	int sz = static_cast<int>(edges.size());
	int ans = 0;
	int cnt = 0;
	for (int i = 0; i < sz; i++)
	{
		int cost = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		if (find(a) != find(b))
		{
			merge(a, b);
			ans += cost;
			cnt++;
		}

		if (cnt - 1 == R * C) break;
	}

	cout << ans << '\n';
}

void solve()
{
	cin >> T;
	while (T--)
	{
		edges.clear();

		cin >> R >> C;
		int node = 0;
		for (int i = 1; i <= R; i++)
		{
			node++;
			for (int j = 1; j <= C - 1; j++)
			{
				int cost;
				cin >> cost;
				edges.push_back({ cost, {node, node + 1} });
				node++;
			}
		}

		node = 0;
		for (int i = 1; i <= R - 1; i++)
		{
			node++;
			for (int j = 1; j <= C; j++)
			{
				int cost;
				cin >> cost;
				edges.push_back({ cost, {node, node + C} });
				if(j != C) node++;
			}
		}

		//for (auto p : edges)
		//{
		//	cout << p.second.first << "," << p.second.second << " : " << p.first << endl;
		//}
		//cout << endl;

		kruskal();
	}
}

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

	solve();
	return 0;
}

lcr7324 2년 전 1

8번 줄과 28번 줄을 다시 보세요.

paparoni 2년 전 0

@lcr7324

제가 미천했네요..

정말 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이거는 왜 4점일까요? (스포조심!)

paparoni 2년 전 0

lcr7324 2년 전 1

paparoni 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말