Algorithm 공부 #18 - 그래프(최소 신장 트리)

 

 

Algorithm 공부 #18 - 그래프(최소 신장 트리)

 

 

최소 신장 트리(minimum spanning tree)

  ● 그래프에서 모든 노드를 연결할 때 사용한 에지들의 가중치의 합을 최소로 하는 트리

  ● 사이클이 포함되면 최소 가중치를 계산할 수 없으므로 사이클을 포함시키지 않는다

  ● N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 N-1개

  ● 최소 신장 트리 구현 방법

      1. 에지 중심으로 저장하므로 에지 리스트로 그래프 표현, 사이클 표현을 위해 유니온 파인드도 함께 사용

      2. 그래프를 가중치를 기준으로 오름차순 정렬

      3. 가중치가 낮은 에지부터 연결하기(이때 바로 연결하지 않고 두 노드의 사이클 여부를 판단해야 함)

      4. 사이클이 생성되지 않는다면 두 노드를 연결, 사이클이 생기면 연결하지 않는다       

      5. 과정 3~4를 에지의 개수가 n-1개가 될 때까지 반복

 

 

 

백준 1197번 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

  ※ 최소 신장 트리 구현 문제 ※

 ● 우선순위 큐로 에지 리스트 구현 

 ● 에지 정보 구조체 생성, 가중치 값 기준 오름차순 정렬로 설정

 ● 유니온 파인드 함수 이용하기

 ● 노드개수-1만큼 반복하면서 시작 노드와 도착 노드의 부모가 다르다면 두 노드를 연결

 ●두 노드를 연결했다면 sum에 가중치를 더해주기

 

#include<iostream>
#include<vector>
#include<queue>
using namespace  std;
typedef struct edge {
	int start, end, value; // 시작 노드, 도착 노드, 가중치
	bool operator> (const edge & temp) const { 
		return value > temp.value; // 가중치 값 기준 오름차순으로 정렬
	}
}edge;
vector<int>parent;
void Union(int start, int end);
int find(int a);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int V, E;
	cin >> V >> E;
	parent.resize(V + 1); // parent배열 크기 조절
	for (int i = 0; i <= V; i++) // parent배열 초기화
		parent[i] = i;

	priority_queue<edge, vector<edge>, greater<edge>>pq; // 우선순위 큐 생성
	for (int i = 0; i < E; i++) { // 에지 리스트 정보 입력
		int start, end, value;
		cin >> start >> end >> value;
		pq.push(edge{ start,end,value });
	}

	int count = 0, sum = 0; // 에지의 개수와 결과 변수
	while (count < V - 1) {
		edge cur = pq.top();
		pq.pop();
		if (find(cur.start) != find(cur.end)) { // 두 노드의 부모가 다르다면 연결
			Union(cur.start, cur.end); // 합치기
			count++; // 에지개수 더해주기
			sum += cur.value; // 가중치 더해주기
		}
	}
	cout << sum;
}
void Union(int start, int end) { // 대표 노드끼리 연결
	int node1 = find(start);
	int node2 = find(end);

	if (node1 != node2)
		parent[node2] = node1;
}
int find(int a) { // 부모 찾기 함수
	if (a == parent[a])
		return a;
	else
		return parent[a] = find(parent[a]);
}

 

 

 

백준 17472번 다리 만들기2

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

17472번: 다리 만들기 2

● 최소 신장 트리, bfs, 유니온 파인드를 이용해야 함

● 먼저 섬을 영역별로 숫자를 다르게 하기 위해서 bfs를 돌려서 각 섬의 영역들을 구분해주기

● 그다음 각 섬들에서 상하좌우로 다리를 뻗어 다른 섬에 도착하면 출발점과 도착점 그리고 다리의 개수 저장

● 우선순위 큐에 위의 정보들을 저장한 뒤 최소 신장 트리를 구성

● 사용한 에지의 개수가 N-2면 다리의 총합을 출력하고 아니라면 노드를 다 연결하지 못한 것이므로 -1출력

 

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

void munion(int a, int b);
int find(int a);
void BFS(int i, int j);

static int dr[] = { -1, 0, 1, 0 };
static int dc[] = { 0, 1, 0, -1 };
static int map[101][101];
static bool visited[101][101] = { false, };
static vector<int> parent;
static int N, M, sNum;
static vector < vector <pair<int, int>> > sumlist;
static vector <pair<int, int>>  mlist;

typedef struct Edge 	// 에지정보 struct 생성, 가중치 값 기준 오름차순 정렬로 설정
{
    int s, e, v;
    bool operator> (const Edge& temp) const {
        return v > temp.v;
    }
}Edge;

static priority_queue<Edge, vector<Edge>, greater<Edge>> pq;   // 오름차순 정렬

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j]; 	// 맵 정보 저장
        }
    }
    sNum = 1;

    for (int i = 0; i < N; i++) { 	// 각 자리에서 BFS 탐색을 이용하여 섬들을 분리하여 줍니다.
        for (int j = 0; j < M; j++) {
            if (map[i][j] != 0 && visited[i][j] != true) {
                BFS(i, j);
                sNum++;
                sumlist.push_back(mlist);
            }
        }
    }

    for (int i = 0; i < sumlist.size(); i++) {	 // 섬의 각 지점에서 만들 수 있는 모든 간선을 저장
        vector<pair<int, int>> now = sumlist[i];
        for (int j = 0; j < now.size(); j++) {
            int r = now[j].first;
            int c = now[j].second;
            int now_S = map[r][c];
            for (int d = 0; d < 4; d++) { 	// 4방향 검색
                int tempR = dr[d];
                int tempC = dc[d];
                int blenght = 0;
                while (r + tempR >= 0 && r + tempR < N && c + tempC >= 0 && c + tempC < M) {
                    if (map[r + tempR][c + tempC] == now_S) 	// 같은 섬이면 간선을 만들 수 없음
                        break;
                    else if (map[r + tempR][c + tempC] != 0) { 	//같은 섬이 아니고 바다가 아니면 
                        if (blenght > 1) 	// 다른 섬 -> 길이가 1이상일때 간선으로 더해줍니다.
                            pq.push(Edge{ now_S, map[r + tempR][c + tempC], blenght });
                        break;
                    }
                    else 	//바다이면 다리의 길이를 연장하여 줍니다.
                        blenght++;
                    if (tempR < 0)tempR--;
                    else if (tempR > 0)tempR++;
                    else if (tempC < 0)tempC--;
                    else if (tempC > 0)tempC++;
                }
            }
        }
    }

    parent.resize(sNum);
    for (int i = 0; i < parent.size(); i++) {
        parent[i] = i;
    }
    int useEdge = 0;
    int result = 0;
    while (!pq.empty()) {  	// 최소 신장 트리 알고리즘을 수행하여 줍니다.
        Edge now = pq.top();
        pq.pop();
        if (find(now.s) != find(now.e)) 	// 같은 부모가 아니라면 -> 연결 가능
        {
            munion(now.s, now.e);
            result = result + now.v;
            useEdge++;
        }
    }
    // 배열에서 쉬운 index 처리를 위해 sNum을 1부터 시작하였으므로 현재 sNum의 값이 섬의 개수보다 1 많은 상태임 때문에 1작은 수가 아닌 2작은 수와 사용 에지를 비교하여 줍니다. 
    if (useEdge == sNum - 2) {
        cout << result << "\n";
    }
    else {
        cout << -1 << "\n";
    }

}

void munion(int a, int b) { 		// union 연산 : 대표 노드끼리 연결하여 줌
    a = find(a);
    b = find(b);
    if (a != b) {
        parent[b] = a;
    }
}
int find(int a) { 	// find 연산
    if (a == parent[a])
        return a;
    else
        return parent[a] = find(parent[a]); 	// 재귀함수의 형태로 구현 -> 경로 압축 부분
}

void BFS(int i, int j) {	 // BFS를 통하여 연결된 섬을 찾아줍니다.
    queue<pair<int, int>> myqueue;
    mlist.clear();
    myqueue.push(make_pair(i, j));
    mlist.push_back(make_pair(i, j));
    visited[i][j] = true;
    map[i][j] = sNum;
    while (!myqueue.empty()) {
        int r = myqueue.front().first;
        int c = myqueue.front().second;
        myqueue.pop();
        for (int d = 0; d < 4; d++) { 	//4방향 검색
            int tempR = dr[d];
            int tempC = dc[d];
            while (r + tempR >= 0 && r + tempR < N && c + tempC >= 0 && c + tempC < M) {
                //현재 방문한 적이 없고 바다가 아니면 같은 섬으로 취급
                if (visited[r + tempR][c + tempC] == false && map[r + tempR][c + tempC] != 0) {
                    int now_i = r + tempR;
                    int now_j = c + tempC;
                    map[now_i][now_j] = sNum;
                    visited[now_i][now_j] = true;
                    mlist.push_back(make_pair(now_i, now_j));
                    myqueue.push(make_pair(now_i, now_j));
                }
                else break;
                if (tempR < 0)tempR--;
                else if (tempR > 0)tempR++;
                else if (tempC < 0)tempC--;
                else if (tempC > 0)tempC++;
            }
        }
    }
}

 

 

 

백준 1414번 불우이웃돕기

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

1414번: 불우이웃돕기

● 입력받을 때 문자를 정수로 처리하는 것이 핵심

● 문자가 소문자일때 대문자일때 0일때를 나누어서 큐에 푸쉬해주기

● 최소신장트리를 구한 후 랜선개수의 총합에서 컴퓨터를 연결하는데 필요한 랜선개수의 최솟값을 뺀 값을 출력

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

void Union(int start, int end);
int find(int a);
vector<int>parent;
typedef struct edge {
	int start, end, value;
	bool operator > (const edge& temp) const {
		return value > temp.value;
	}
}edge;
vector<vector<int>>map;
priority_queue<edge, vector<edge>, greater<edge>>pq;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N,sum=0;
	cin >> N;
	map.resize(N + 1);
	parent.resize(N + 1);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			char tempc = cin.get();
			if (tempc == '\n') {
				tempc = cin.get();
			}
			int temp = 0;
			if (tempc >= 'a' && tempc <= 'z') {
				temp = tempc - 'a' + 1;
			}
			else if (tempc >= 'A' && tempc <= 'Z') {
				temp = tempc - 'A' + 27;
			}
			sum = sum + temp; 	// 총 랜선의 길의 저장
			if (i != j && temp != 0) {
				pq.push(edge{ i, j, temp });
			}
		}
	}
	
	for (int i = 0; i <= N; i++)
		parent[i] = i;

	int Ncount = 0;
	int Nsum = 0;
	while (!pq.empty()) {
		edge cur = pq.top();
		pq.pop();
		if (find(cur.start) != find(cur.end)) {
			Union(cur.start, cur.end);
			Nsum += cur.value;
			Ncount++;
		}
	}
	if (Ncount == N - 1)
		cout << sum-Nsum;
	else
		cout << -1;
}

void Union(int start, int end) {
	int node1 = find(start);
	int node2 = find(end);

	if (node1 != node2)
		parent[node2] = node1;
}
int find(int a) {
	if (parent[a] == a)
		return a;
	else
		return parent[a] = find(parent[a]);
}