MST(Minimum Spanning Tree 최소신장 트리) Kruskal 알고리즘

MST : Minimum spanning tree

그래프에서 최소비용으로 모든 구간을 연결한 트리

MST 의 특징

트리이기 떄문에 cycle 존재하면 안된다.

답은 여러개가 될수 있다.

KRUSKAL 알고리즘 요약

MST를 구하는 대표적인 알고리즘

시간복잡도는 O(N logN) 여기서 n은 연결되는 간선의 수를 뜻한다.

크루스칼 알고리즘 과정

가중치 값을 기준으로 정렬을 먼저 한다.

Union Find 자료구조를 이용해서 간선을 선택해준다.

크루스칼 알고리즘 과정 1

그래프를 아래와 같이 하드코딩 해준다.

v1,과 v2의 순서는 반대여도 상관이 없다.

정렬하기

간선선택하기

1중 for문을 돌리면서 MST가 될 간선을 경정짓는다.

맨앞에 잇는 C-B간산은 MST 간선으로 채택된다.

노드 C와 B는 같은 그룹이된다(Union Find알고리즘 사용)

E-D 간선이 선택되고, E-D 가 같은 그룹인지 확인한후 아니라면 같은 그룹이 된다.

E-D은 간선 채택이 된다.

E-B에서 E,B는 각각 다른 그룹이기에 같은 그룹으로 만들고 간선 채택시킨다.

C-D는 같은 그룹이다. 같은 그룹인 노드를 연결시키면 Cycle이 발생하게 된다.

간선으로 채택하지 않고 넘어간다.

이와 같은 방법으로 나머지 간선정보들을 전부 순회한후 연결시켜주면 MST가 완성된다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>



struct Node
{
	char v1;
	char v2;

	int cost;
};

std::vector<Node> graph = 
{
	{'A', 'B', 6},
	{'A', 'C', 4},
	{'A', 'D', 5},
	{'C', 'B', 1},
	{'C', 'D', 3},
	{'C', 'E', 7},
	{'E', 'B', 3},
	{'E', 'D', 1}
};

int n = 8; //간선의 갯수

bool compare(Node a, Node b)
{
	return a.cost < b.cost;
}

int org[200] = {};


int findParent(int now)
{
	if (org[now] == 0)
	{
		return now;
	}
	
	int ret = findParent(org[now]);
	org[now] = ret;
	return ret;
}

int unionOrg(int v1, int v2)
{
	int p1 = findParent(v1);
	int p2 = findParent(v2);

	if (p1 == p2)
	{
		return 0;
	}

	org[p1] = p2;
	return 1;
}


int main()
{
	std::sort(graph.begin(), graph.end(), compare);

	int cnt = 0;
	int sum = 0;

	for (size_t i = 0; i < graph.size(); i++)
	{
		if (unionOrg(graph[i].v1, graph[i].v2))
		{
			sum += graph[i].cost;
			cnt++;
		}
	}

	if (cnt == 4/*노드의개수 - 1 */)
	{
		std::cout << sum << std::endl;
	}

	return 0;
}
JavaScript
복사

연습문제

문제 1번

수학이는 일반적인 사칙연산이 마음에 들지 않았습니다.

자신만의 사칙연산을 만들어 세상에 널리 알리고 싶어합니다.

연산자	설명	예시
!!	2회 더한다.	1 !! 3 = 7
#	2회 뺀다.	5 # 1 = 2
$	무조건 10을 더한다.	3 $ 8 = 13
&	두번째 숫자 2승 후 더한다.	2 & 3 = 11
^	답은 무조건 0	3 ^ 7 = 0

수학이는 자신이 만든 연산자를 사용해야하는 빈칸 채우기 문제를 냈습니다.

숫자1 [__] 숫자2 [__] 숫자3 >= 20

숫자 3개를 입력받고, 숫자 3개 사이에 2개의 연산자를 사용합니다.

이렇게 구해진 수가 20보다 큰 수를 찾는 수식입니다.

우리는 5개 연산자 중 2개를 선택하여, 조건을 만족 시켜야합니다.

조건을 만족시킬 수 있는 총 경우의 수를 출력 해 주세요.

(Backtracking을 사용하여 문제를 풀어주세요.)

[입력]

숫자1, 2, 3을 입력 받으세요.

[출력]

결과 값이 20이 이상이 되는 경우의 수를 출력하세요.

[예제]

1 5 2 를 입력 받았을때 !! 와 $ 연산자를 사용하면

1 !! 5 $ 2 = 21 이 되고, 이는 20보다 크므로 조건을 만족시킬 수 있습니다.

입력 예제

1 5 2

출력 결과

문제 2번

바이러스를 투여하고, 바이러스가 모두 퍼지고 난 뒤의 결과를 출력해주세요.

바이러스는 두 곳에 투여되며, 상, 하, 좌, 우 네 방향으로 퍼지게 됩니다.

바이러스가 퍼지는 맵의 크기는 3 X 3 입니다.

[입력]

바이러스가 투여되는 좌표 Y X 두곳을 입력하세요.

[출력]

바이러스가 모두 퍼지고 난 뒤의 상태를 출력해주세요.

[예시 1]

(0, 0) 과 (2, 2) 에 바이러스를 투여한다면 아래처럼 바이러스는 상하좌우 네 방향으로 퍼지며, 강도는 1씩 증가합니다.

(0, 0) 과 (2, 2) 에서 바이러스가 모두 퍼지면 위와 같은 결과가 출력되어야 합니다.

[예시 2]

만약 (2, 1) (2, 2)에 바이러스를 투여한다면 아래와 같은 결과가 출력되어야 합니다.

입력 예제

0 0

2 2

출력 결과

123

232

321

문제 3번

시작 좌표에서 종료 좌표까지 최소 몇 회만에 갈 수 있는지 확인해주세요.

BFS 알고리즘을 사용하여 길을 찾아주세요.

아래 1의 위치로는 이동할 수 없습니다.

2차원 배열의 맵은 하드코딩하여 풀어 주세요.

[입력]

시작 좌표 Y X 와, 그 다음 줄에 종료 좌표 Y X 를 입력하세요.

[출력]

시작 좌표 부터 종료 좌표까지 최소 몇번 만에 도착할 수 있는지 출력해주세요.

[예시 1]

시작 좌표 (0, 0) 과 도착 좌표 (3, 3) 이 입력 될때, 결과는 6회입니다.

입력 예제

0 0

3 3

출력 결과

6회

문제 4번

(0, 0)에 서있는 쥐는 치즈를 먼저 먹고, 친구를 만나러 가려고 합니다.

쥐는 ↑↓ ← → 로 이동 할 수 있습니다.

[입력]

치즈 위치 (Y, X) 와 친구 좌표 (N, M) 을 입력 받으세요.

[출력]

친구를 만나기까지의 최단 거리를 출력 해주세요.

한 칸을 이동했을때가 1입니다.

[예시]

위 예제에서는 9회 이동으로 치즈를 먹고 친구를 만날 수 있습니다.

입력 예제

2 0

0 3

출력 결과

문제 5번

4 x 6 사이즈의 맵에 있는 모든 치킨을 먹으려고 합니다.

지혁이는 [0, 0]에서 출발하고, ↑↓ ← → 방향으로 이동할 수 있습니다.

1은 벽이라 이동할 수없습니다.

2는 고기 입니다.

0으로 표시된 지역만 이동할 수 있습니다.

[입력]

4 X 6 의 2차원 배열 정보를 입력 받으세요.

[출력]

치킨을 총 몇 마리 먹을 수 있는지 출력하세요.

입력 예제

0 0 1 2 1 2

1 0 0 1 0 1

0 0 1 2 0 0

2 0 0 0 0 0

출력 결과

문제 6번

현준이가 설치한 폭죽은 1초당 한번씩 불꽃이 사방으로 퍼져나갑니다.

폭죽이 한번 터질 때 마다 8방향 으로 터져 나가고, 연달아 8 방향 (⬉⬈⬊⬋)으로 또 터집니다.

만약 0초에 폭죽이 1개 있다면,

1초에는 폭죽이 8개 불꽃으로 터집니다.

2초에는 8개 불꽃이 각각 8개씩 64개로 퍼집니다.

3초에는 64개 불꽃은 64 x 8 = 512개로 퍼집니다.

먼저 4 x 5 사이즈의 맵을 입력 받으세요.

0은 빈 하늘을, 1은 폭죽을 의미합니다.

[입력]

4 X 5 사이즈의 맵을 입력 하세요.

[출력]

하늘 전체를 불꽃으로 채우는데 걸리는 시간을 출력 해주세요.

[예시 1]

[1초 경과]

[2초 경과]

[3초 경과]

예시 1에서 하늘을 불꽃으로 모두 채우는데 걸리는 시간은 3초 입니다.

입력 예제

0 0 1 0 1

0 0 0 0 0

0 1 0 0 0

0 0 0 0 0

출력 결과

문제 7번

지효는 땅이 얼마나 큰지 알아내는 드론을 띄웠습니다.

↑ ↓ ← → 으로 땅이 붙어있는 경우는 같은 땅입니다.

[입력]

4x4 땅 상태를 입력 받아 주세요.

[출력]

(0, 0) 부터 상, 하, 좌, 우 네 방향으로 붙어있는 땅의 총 개수를 출력해주세요.

입력 예제

1 1 0 1

0 1 0 1

0 1 1 0

1 0 0 0

출력 결과

문제 8번

아래와 같은 숫자 노드 그래프를 인접 행렬로 하드 코딩해주세요.

그리고 입력받은 노드부터 BFS를 이용하여 노드의 값을 출력해주세요.

BFS 알고리즘을 사용하여 탐색했을때, 작은 숫자의 노드부터 탐색하기 때문에

출발지가 3인 예제의 답은 3 1 6 8 4 2 9 7 입니다.

[입력]

출발지를 입력 받으세요.

[출력]

BFS 로 탐색하면서 순서대로 노드 값을 출력하세요.

입력 예제

출력 결과

3 1 6 8 4 2 9 7

문제 9번

위의 맵배열을 하드코딩 한 후,

시작 위치와 도착지점을 입력 받으세요. (y, x)

최소 몇칸만에 갈 수 있는지 DFS를 돌려 답을 구해주세요.

입력 예제

0 0

3 3

출력 결과

DFS 응용 문제들을 풀어봅니다. DFS 문제들을 설계 할 때는 다음과 내용들을 미리 정의 해 둡시다.

트리 형태를 그려, Branch / Level이 몇 개인지 명확히 명시하기

바닥조건 / 가지치기 조건을 명확히 하기

추가 함수를 구현하는 것이 더 좋을 지 생각 해 보기

원상복구를 어떻게 구현할지

함수 Interface 결정

문제 1번

3 x 3 숫자판에서 3개의 숫자를 선택해야 합니다.

-4	1	3
3	-1	4
-3	2	0

3 x 3개의 숫자를 입력 받습니다.

선택된 3개의 숫자의 곱이 MAX인 값을 찾고,

MAX가 되는 수가 총 몇 가지 조합이 있는지 출력 해 주세요.

아래 예제에서는 MAX값이 나오는 조합이 총 4개 있습니다.

[예제]

아래 예제에서는 총 7가지 조합이 있습니다.

입력 예제

•

4 1 3

3 -1 4

•

3 4 0

출력 결과

문제 2번

뒷산에서 수 많은 한약 재료들을 배열에 담아왔습니다.

최대 20자리의 대문자로 구성된 문자열을 입력받아주세요.

이곳에 쓰인 알파벳(재료)들을 선정해서 세 자리로 구성된 새로운 조합(한약)을 만들어보려고 합니다.

사전 순으로, 중복없이 만들어지는 모든 조합을 출력 해 주세요.

입력 예제

ZFAABABBAB

출력 결과

AAA

AAB

AAF

AAZ

ABB

ABF

ABZ

AFF

AFZ

AZZ

BBB

BBF

BBZ

BFF

BFZ

BZZ

FFF

FFZ

FZZ

ZZZ

문제 3번

위 메뉴에서 5개의 음료 중 n개를 골라, 10,000원 어치 구매하려고 합니다.

n개를 항상 같은 수량으로 최대한 구매해야 한다면 얻을 수 있는 MAX 포인트는 얼마일까요?

예를들어

만약 n = 2 이고, 아메리카노(500원, 30p) 모히토(700원, 10p) 선택해서 10,000원 어치 최대로 구매하면

얻을 수 있는 포인트 값은 아래와 같습니다.

1,200원 x 8 = 9,600원 | 40p x 8 = 320 포인트 입니다.

입력 예제

출력 결과

600

문제 4번

디아블로 퍼즐이 있습니다. 이 퍼즐을 풀면 악마가 깨어납니다.

아래와 같이 Z 기준으로 한번 돌리면 Z를 둘러싸고 있는 문자들이 회전합니다.

가로로 AAA가 맞춰지면 퍼즐이 맞춰진 것 입니다.

퍼즐 상태를 입력받고

정확히 6회 안에(6회 포함) 퍼즐을 맞출 수 있는지 판단하는 프로그램을 작성해주세요.

맞출 수 있으면 가능, 그렇지 않으면 불가능이라고 출력 합니다.

예를 들어

아래 예제에서는 ①~④ 번 까지 선택 할 수 있고, 선택하면 퍼즐이 시계방향으로 돌아갑니다.

② 를 한번 돌립니다. ③ 을 한번 돌립니다. ② 를 한번 돌립니다.

3번 만에 가로로 AAA가 맟춰졌습니다. 디아블로가 깨어날 가능성이 있습니다.

입력 예제

ABTB

ATCD

BGAD

ABCT

출력 결과

가능

문제 5번

시어머니와 며느리는 명절을 맞아 고기를 굽고 있습니다.

O는 앞면, X는 뒷면 입니다.

고기의 상태를 입력받습니다.

시어머니가 고기를 뒤집을 곳을 지목합니다.

며느리는 지목 당한 곳과 양쪽 좌우를 모두 뒤집습니다.

아래 예제는 총 두번만에 고기를 모두 같은 방향으로 고기를 뒤집을 수 있습니다.

만약 시어머니가 가장자리를 선택했다면,

며느리는 2개의 고기만 뒤집습니다.

시어머니와 며느리는 최소 몇 번 고기를 뒤집어서,

모두 같은 방향 (전체 OOOO... 또는 전체 XXXX...) 으로 만들 수 있을까요?

모두 같은 방향으로 뒤집는 최소 횟수를 출력 해 주세요.

만약 4회 만에 뒤집는 것을 실패한다면 impossible 이라고 출력 해 주세요.

[세부조건]

고기의 개수는 최대 20개 까지 될 수 있습니다.

입력 예제

OXOOX