Programmers [섬 연결하기] - 분명 Prim's algorithm...? 을 짰는데..

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
int arr[100][100];
int visit[100];
priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> q;

int solution(int n, vector<vector<int>> costs) {
	int answer = 0, cur, s = costs.size();
	bool flag = false, skip = false;
	pair<int,int> temp;

	if (n == 1)	{return 0;}
	for (int i = 0; i < s; i++) {
		arr[costs[i][0]][costs[i][1]] = costs[i][2];
		arr[costs[i][1]][costs[i][0]] = costs[i][2];
	}
	cur = costs[0][0];
	visit[cur] = true;
	q.push(make_pair(0, cur));

	temp = q.top();
	while (1) {
		q.pop();
		if(!skip)
			for (int i = 0; i < n; i++) {
				if (arr[cur][i] != 0 && !visit[i])
					q.push(make_pair(arr[cur][i], i));
			}
		skip = false;
		temp = q.top();
		if (!visit[temp.second])
		{
			answer += temp.first;
			visit[temp.second] = true;
			for (int i = 0; i < n; i++) {
				if (visit[i] == false) {
					flag = true;
					break;
				}
			}
			if (!flag)
				break;
			flag = false;
			cur = temp.second;
		}
		else
			skip = true;
	}
	cout << answer;
	return answer;
}

int main() {
	int n =4;

	vector<vector<int>> costs = {{0,1,1},{0,2,2}, {1,2,5}, {1,3,1}, {2,3,8}};
	solution(n, costs);

	return 0;
}

 

알고리즘 문제를 풀면서 가장 큰 쾌감을 얻을 때는 몇 가지 case가 있다.

보통 한번에 풀리거나 완벽한 알고리즘 깔끔하게 구현했을 때 역시 쾌감을 얻겠지만, 나의 경우는 그런 경우보다는 오히려 밍기적 거리며 짜는 코드가 더 큰 쾌감을 주는듯하다.

 

생각한 것을 그대로, 조금 돌아가더라도 내가 구상한 것을 그대로 투영하는 것이 진짜 큰 성취감이 온다.

물론 구상한 것이 틀리다면 수정을 거쳐가야하겠지만 그래도 처음 구상한 것의 큰 틀은 바꾸지 않고 진행하는 편이다.

 

노빠꾸

짜고 나면 더럽기도 하고, 쓸데없이 bool 변수가 많아지기도 하지만, 그대로 진행...

 

짜다가, '아 이건 그렇게 푸는거구나' 하고 감이 오더라도, 이어서 드는 '근데 이것도 될 것 같은데?'라는 오기(똥고집)가 생긴다.

물론 100% 성공하는 것은 아닌데, 하면 할수록 확률은 오르는 느낌이다.(구현력이 올라가서일 수도..)

 

이 문제 같은 경우는 문제를 풀던 도중에 어디선가 흐릿하게 기억나는 알고리즘이 생각나서 구현을 하다가 친구한테 이러이러한 알고리즘인데, 이름이 뭐였더라... 하고 물었더니 Prim과 MST가 바로 튀어나오더라(똑똑한 친구...)

 

쨋든 이름은 알았고, 분명 전에 배웠는데 흐릿해서 그런지 깔끔하게 잘 안돼다가 꾸역꾸역 해서 완성시키고, 실제 프림과는 어떻게 다른가.. 하고 확인하니 놀랍게도

 

끝내주게 다르다.(ㅋㅋㅋㅋㅋㅋㅋㅋ)

 

돌아가기는 돌아가니 신기하기도 하고 그래도 밀고 나가서 성공한 성취감도 있으니 not bad 하다.