글 읽기 - 17472번 다리만들기2 dfs, MST로 풀었는데 반례좀 찾아주세요 ㅠ

bjw2761 3년 전 0

dfs, MST로 풀었는데 반례가 있나요..? 왜 틀린지 모르겟어요

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

int map[10][10];
int n, m;
vector<pair<int, pair<int, int > > > bridges;
int dy[4] = { -1,1 ,0 ,0 };
int dx[4] = { 0,0,-1,1 };
int parent[7];

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

void unionset(int a, int b)
{
	a = getParent(a);
	b = getParent(b);
	parent[a] = b;
}


void getMindist(int u, int v)
{
	queue<pair<int, int> > q;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (map[i][j] == u) q.push({ i,j });
	
	int mindist = 10;
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int new_y = y + dy[i];
			int new_x = x + dx[i];
			int dist = 0;
			if (new_y < 0 || new_y >= n || new_x < 0 || new_x >= m) continue;
			if (map[new_y][new_x] == u) continue;
			while (1)
			{
				if (map[new_y][new_x] == 0)
				{
					dist++;
					new_y += dy[i];
					new_x += dx[i];
				}
				else if (map[new_y][new_x] == v)
				{
					if (dist > 1 && mindist > dist) mindist = dist;
					break;
				}
				else {
					break;
				}
			}
				


		}
	}
	if(mindist!=10) bridges.push_back({ mindist , {u,v} });
	

}

void fillmap(int y, int x, int number)
{
	if (y < 0 || y >= n || x < 0 || x >= m) return;
	if (map[y][x] != -1) return;

	map[y][x] = number;

	fillmap(y - 1, x, number);
	fillmap(y + 1, x, number);
	fillmap(y, x - 1, number);
	fillmap(y, x + 1, number);
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int num;
			cin >> num;
			if (num == 1) map[i][j] = -1;
		}
	}
	
	int number = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == -1) {
				fillmap(i, j, ++number);
			}
		}
	}
	for (int i = 1; i <= number - 1; i++)
	{
		for (int j = i + 1; j <= number; j++)
		{
			getMindist(i, j);
		}
	}

	sort(bridges.begin(), bridges.end());

	for (int i = 1; i <= number; i++) parent[i] = i;

	int size = bridges.size();
	int index = 0;
	int cnt = 0;
	int dist, s, e;
	int sum = 0;
	while (cnt <number-1)
	{
		if (size == index) {
			cout << "-1\n";
			return 0;
		}
		dist = bridges[index].first;
		s = bridges[index].second.first;
		e = bridges[index].second.second;
		index++;

		if (getParent(s) == getParent(e)) continue;
		else {
			unionset(s, e);
			cnt++;
			sum += dist;
		}

	}
	cout << sum << "\n";

	

}

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

문제

문제

출처

ICPC

17472번 다리만들기2 dfs, MST로 풀었는데 반례좀 찾아주세요 ㅠ

bjw2761 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말