풀이

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


int m, n;

pair<long, pair<int, int>> edge[200001];
int parents[200001];

long res=0;
int edgenum = 0;


int FindRoot(int x)
{
	if (x == parents[x])
		return x;
	return parents[x] = FindRoot(parents[x]);
}

void Merge(int x, int y)
{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x == y)
		return;
	parents[x] = y;
}


int main()
{


	int x, y, z;


	while(1)
	{
		edgenum = 0;
		res = 0;


		cin >> m >> n;

		
		if (m == 0 && n == 0)
			break;


		for (int i = 0; i <= n; i++)
		{
			parents[i] = i;
			edge[i] = { 0,{0,0} };
		}



		for (int i = 0; i < n; i++) 
		{
			cin >> x >> y >> z;

			edge[i] = { z,{x,y} };
			res += z;

		}


		sort(edge, edge + n);


		for (int i = 0; i < n; i++)
		{
			if (FindRoot(edge[i].second.first) == FindRoot(edge[i].second.second))
				continue;

			Merge(edge[i].second.first, edge[i].second.second);
			res -= edge[i].first;

			edgenum++;
			if (edgenum == m - 1)
				break;
		}

		cout << res<<'\n';


	}

}

위의 문제에서 입력부분을 잘 보면  "입력은 여러 개의 테스트 케이스로 구분되어 있다." 라는 말이 있습니다.

네, 이 말 때문에 몇번 틀렸습니다. 

저는 백준문제들의 정답비율을 낮추는데에 한번 더 공헌을 했습니다.

입력받는 부분을 무한반복문으로 돌리면서 0,0을 입력받으면 끝나게 해야합니다. 저는 오히려 "도시상의 모든 길의 거리 합은 231미터보다 작다." 같은 자료형 범위를 유심히 살피다가 오히려 근본적인 문제에서부터 잘못된거죠..(´。＿。｀)..

그래도 푸는데 따로 어려운점은 없었습니다. 바로 직전에 풀었던 최소스패닝트리와 매우 유사합니다.

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

풀이

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


int V, E;
pair<int, pair<int, int>> edge[100001];
int parents[10001];

int res;
int edgenum = 0;


int FindRoot(int x)
{
	if (x == parents[x])
		return x;
	return parents[x] = FindRoot(parents[x]);
}

void Merge(int x, int y)
{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x == y)
		return;
	parents[x] = y;
}


int main()
{
	for (int i = 0; i < 10001; i++)
	{
		parents[i] = i;
	}


	cin >> V >> E;

	int a, b, c;

	for (int i = 0; i < E; i++)
	{
		cin >> a >> b >> c;
		edge[i] = { c,{a,b} };

	}

	sort(edge, edge + E);


	for (int i = 0; i < E; i++)
	{
		if (FindRoot(edge[i].second.first) == FindRoot(edge[i].second.second))
			continue;

		Merge(edge[i].second.first, edge[i].second.second);
		res += edge[i].first;

		edgenum++;
		if (edgenum == V - 1)
			break;
	}

	cout << res;

}

크루스칼 알고리즘을 통해 최소스패닝트리 문제를 풀었습니다. 

스터디에서 공부할때에 그냥 넘어갈만한 pair<int, pair<int, int>> edge 도 코드로 직접 풀면서 보니 왜 int가 먼저 있는지를 한번 더 생각하게되고 sort를 하기위해서 먼저 두었구나라는 답을 찾게되는 거라던가

알고리즘도 FindRoot와 Merge가 중요하다고해서 그 둘만  보고 가져다 쓰면 안되고 그 전에 물밑작업으로 부모배열에 각 숫자를 그대로 대입해주어야 한다는걸 깨닫게 되는 등

실제 눈으로만 보고 이해하는것보단 역시 코드로 적으면서 실행시켜보고 이해하는게 훨씬 이해하기에 빠른것같습니다.

여러모로 간단하지만 몇번씩 더 다시 생각하게하는 코드인것같습니다.

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

풀이

#include<iostream>

using namespace std;

int n,m;//입력값



int road[251][251] = {0};

void FloydWarshall() {
	for (int via = 1; via <= n; via++) {
		for (int from = 1; from <= n; from++) {
			for (int to = 1; to <= n; to++) {		
				 if (road[from][to] > road[from][via] + road[via][to])
					road[from][to] = road[from][via] + road[via][to];
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	


	cin >> n >> m;

	for (int i = 1; i <=n; i++)
	{
		for (int j = 1; j <=n; j++)
		{
			road[i][j] = 1000000000;

		}
	}


	int u, v, b;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v >> b;
		
		road[u][u] = 0;
		road[v][v] = 0;

		road[u][v] = 0;
		if (b == 0)
		{
			road[v][u] = 1;
		}
		else 
		{
			road[v][u] = 0;
		}
			
	}



	FloydWarshall();

	int k;
	cin >> k;
	int s, e;
	for (int i = 0; i < k; i++)
	{
		cin >> s >> e;
		cout << road[s][e]<<'\n';
	}
}

처음에는 못풀어서 다른 사람이 어떻게 풀었는지 코드를 안보고 대충 도입부에 말만 보고 코드를 풀어놓았는데 어쩌다보니 정답비율 낮추는데에 큰 공헌을 했습니다.

처음에는 시간초과라서 

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

이렇게 3줄을 넣어주니 그다음부터는 다행히 시간초과는 뜨지않지만 계속 틀렸습니다의 연속 퍼레이드라서 다른 사람들은 도대체 어떻게 풀었는지 코드를 볼 수 밖에 없었습니다.

근데 다른 사람들의 코드를 봐도 풀이과정이 똑같았고 진짜 진짜 너무 똑같아서 백준은 나만 왕따시키는게 혹시 아닐까 생각을 했지만 마침내 발견했습니다.

요  road[v][v] =0자식 이 자식 때문에 틀렸습니다. 사실 제가 멍청멍청하게 road[u][u] =0 만을 해준게 잘못이긴하지만 저 자식이 너무 교묘하게 숨어있는게 나빳자나여 

다른 사람들의 코드를 보다보니 괜히 입력부에서 0을 해준것같기도 합니다. 너무 좁게만 보고있었기에 반성해야겠습니다.

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

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


int n, m;
bool road[26][26] = { 0 };


char before, after;
string tmp;

void FloydWarshall() {
	for (int via = 0; via < 26; via++) {

		for (int from = 0; from < 26; from++) {
			if (!road[from][via])
				continue;


			for (int to = 0; to < 26; to++) {
				if (!road[from][via])
					continue;


				if (road[from][via] && road[via][to])
					road[from][to] = 1;
				if (!road[from][via] && !road[via][to])
					road[from][to] = 0;
			}
		}
	}
}


int main()
{

	cin >> n;
	for (int i = 0; i < n; i++) 
	{
		cin >> before >> tmp >> after;
		road[before -'a'][after -'a'] = 1;	
	}

	FloydWarshall();

	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> before >> tmp >> after;
		if (road[before - 'a'][after - 'a'] == 1)
			printf("T\n");
		else
			printf("F\n");
	}

}

이 문제는 계속 들여다보다가 결국에 못풀어서 풀이를 봐버렸습니다..

풀이를 보니 cin을 쓰면 훨씬 효율적으로 할 수 있는데.. 괜히 scanf를 잡고있다가 입출력에서 다 진을 뺏겨서 오히려 문제에 집중을 못했던것같습니다. 

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