풀이

#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

플로이드 성공

풀이

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


int n, m;

int road[101][101] = { 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()
{
	scanf("%d", &n);
	scanf("%d", &m);

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			if (i == j)
				road[i][j] = 0;
			else
			road[i][j] = 20000000;
		}
	}

	int a, b, c;
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &a, &b, &c);

		if(road[a][b] > c)
		road[a][b] = c;
	}

	FloydWarshall();

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (road[i][j] == 20000000)
				road[i][j] = 0;
			printf("%d ", road[i][j]);
		}
		printf("\n");
	}
}

한번 틀리고나서 두번째에 맞춘문제입니다. 플로이드와샬 알고리즘이 워낙 명확해서 따로 손을 댄 부분이 없었으나 문제에서 주어진 비용인 100,000 을 최대비용으로 생각하고 초기화를 한게 오답의 원인이었습니다. 

최대비용은 단순히 100,000을 생각하는게 아니라 각 도시마다 걸리는 비용을 생각해야하기에 

도시의 수 * 비용 = 100 * 100,000 을 해야합니다.

저는 단순문제라고 생각했는데 한번 틀렸기때문에 괘씸해서 그냥 20,000,000 해줬습니다. 제 작은 복수입니다.

+) const int MAX = 20000000; 로하고 MAX를 대입하면 효율적이라고한다.

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