Red Salmon

출처 : https://www.acmicpc.net/problem/13418

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.12/13418.cpp

이 문제의 요점은 결국 모든 점을 최소값으로 지나야 한다는 것이다. 

즉 크루스칼 혹은 프림알고리즘을 사용해야 한다. 

정점의 값은 오름막이 0 내림막이 1이다. 나는 처음에 이를 반대로 생각하여 오답을 도출했다.

그래서 이를 수정하기위해 w값을 w=!w로 반전해주어 값을 주었다.

그리고 값은 n^2을 해야 한다는 것을 명심해야 한다.

기본적인 프림 혹은 크루스칼알고리즘을 구현할수있다면 큰 문제없이 풀 수 있는 문제이다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1197.cpp

이 문제는 말 그대로 최소 스패닝 트리이다. 

뭐 없다. 그냥 풀면 된다. 이론에 입각하여 이론대로 크루스칼 알고리즘을 사용하면 답이나온다.

출처 : https://www.acmicpc.net/problem/1922

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1922.cpp

이 문제는 모든 정점을 연결했을 때 최소를 구하라는 것이다. 즉! 크루스칼 또는 프림알고리즘을 구현해라 라는것과 같다. 이것은 최소스패닝트리 문제이며 MST라고도 한다. 

해당 알고리즘에 대한 설명은 구글링을 하면 너무 자세히 나와있기 때문에 굳이 내가 적어야할 필요가 없는것 같다. 

문제 자체도 해당 알고리즘만 구현하면 되는 간단한 문제로써, 모르면 못풀고 알면 푸는 그런 것이다. 

나는 싸이클이 형성되는 간선 체크를 mfind라는 함수를 사용했는데 이게 느릴줄 알았는데 상당히 빠른 속도를 보인다. (자주써야겠다.)

문제 자체는 특별할 것이 없기 때문에 여기서 마친다.