글 읽기 - 스패닝 트리 질문드립니다!

satelites 3년 전 0

문제 다리만들기2를

1. 인접리스트를 만든다.

2. MST를 구한다.

3. 정답을 출력한다.

저는 위와 같이 풀었습니다.

근데 다른 사람 코드를 보니

1. 인접행렬을 만든다.

2. 모든 스패닝 트리를 구한다.

3. 정답을 출력한다.

로 푼 사람이 있더군요.

근데 여기서 궁금해진게, 모든 스패닝 트리를 구하는 알고리즘입니다.

아래 코드는 다른 분이 dfs로 스패닝 코드를 모두 탐색하는 코드입니다. 1에서 2로가는 edge와 2에서 1로가는 edge를 같은 길로 처리하지 않아서 중복이 발생하더라고요.

인접리스트나 행렬 만으로는 이 중복을 처리하는게 불가능한가요? 인접리스트나 행렬만으로 중복없이 모든 가능한 스패닝 트리를 구하는 방법이 있을까용?

#pragma warning (disable : 4996)
#include <cstdio>
#include <vector>
using namespace std;

const int pSize = 4; 
int visited[pSize];
long long ways;
vector<pair<int, int>> adList[pSize];
vector<pair<int, int>> edge;

bool isConnect(int cur, int next) {
	
	for (int i = 0; i < adList[cur].size(); ++i) {
		if (adList[cur][i].first == next) return true;
	}
	return false;
}

void dfs(int dist) {

	if (ways == 0)
		printf("\n");
	bool isAllVisited = true;
	for (int i = 0; i < pSize; i++) {
		if (visited[i] == 0) {
			isAllVisited = false; break;
		}
	}
	if (isAllVisited) {//모두 arrive했다면 정답을 갱신한다.
		for (auto k : edge) {
			printf("(%d, %d) ", k.first, k.second);
		}
		ways+=1;
		printf("\n");
		return;
	}
	
	/*모든 노드를 순회한다.
	어떤 노드에서 시작하냐에 따라 결과가 달라진다.
	*/
	for (int i = 0; i < pSize; ++i) {
		if (visited[i] == 1) {
			for (int j = 0; j < pSize; ++j) {//해당 노드에서 모든 노드까지
				if (i == j) continue; //자기 자신은 PASS
				if (visited[j] == 0 and isConnect(i,j)) {
					visited[j] = 1;
					edge.push_back({ i,j });
					dfs(dist);
					edge.pop_back();
					visited[j] = 0;
				}
			}
		}
	}

	return;
}

int main() {
	{
		adList[0].push_back({ 1,2 });//0번
		adList[0].push_back({ 3,2 });

		adList[1].push_back({ 0,2 });//0번
		adList[1].push_back({ 2,3 });

		adList[2].push_back({ 0,4 });
		adList[2].push_back({ 1,3 });
		adList[2].push_back({ 2,1 });

		adList[3].push_back({ 0,2 });
		adList[3].push_back({ 2,1 });
	}

	for (int i = 0; i <= pSize; i++) {
		visited[i] = 1;
		dfs(0);
		visited[i] = 0;
	}
	printf("%d", ways);
	return 0;
}

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

문제

문제

출처

ICPC

스패닝 트리 질문드립니다!

satelites 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말