크러스컬 알고리즘에 대하여 (정보올림피아드 2016)

크러스컬 알고리즘(Kruskal’s algorithm)이란?

최소 비용 생성나무를 찾는 알고리즘이라고 볼수 있다.

일단 우리는 크러스컬 알고리즘을 구현하는 방법에 대하여 알아보겠다.

크러스컬 알고리즘은 다음 순서로 작동한다

1. 그래프의 각 꼭짓점이 각각 하나의 나무가 되도록 하는 숲A 를 만든다.

2. 모든 변을 원소로 하는 집합 S를 만든다.

3. 집합 S 가 비어있지 않는 동안

- 가장 작은 비용의 변을 S에서 하나 뺀다.

- 그 변이 어떤 두개의 나무를 연결한다면 두 나무를 연결하여 하나의 나무로 만든다.

- 그렇지 않다면 그 변은 버린다.

일단 위키피디아의 말을 보면 어렵게 느껴진다. 그래서 직접 문제를 가져왔다.

크리스컬 알고리즘을 실제로 사용하자!

이 문제는 정보올림피아드 2016년 중고등부 문제 7번이다.

먼저,

가장 비용이 적은 변을 고른다. (변 HG가 그 변이다)

그 후 다음으로 비용이 가장 적은 변을 고른다.변 CI와 변 GF가 그 변이다.)

이와 같은 방법으로 점점 비용이 적은 변들을 순서대로 체크한다.

그러나 쓸데없는곳 즉,고리를 생성하지 않는 변을 골라야한다

알려준 순서대로 문제를 풀게되면

이 다음순서로 비용이 6인 변을 체크하게 되는데

비용이 6인 변을 체크하게되면

이미 다른 변들로 연결된 G도시와 I도시가 또 연결되어 비용을 날리게 된다.

그러므로 그것에 유의하여 도시들을 연결하다보면

이와 비슷한

최소비용이 1+2+2+4+4+7+8+9

즉, 37이 되도록 연결한 그림이 그려진다.

따라서 정답은 3번 37이다.

이렇게 크리스컬 알고리즘이 무엇이고 어떻게 실행되는지

정보올림피아드 2016 7번 문제를 통해 알아보았다.

(티스토리를 시작한지 얼마 되지않아 필력이 부족한것 같습니다..)