코딩무식자 전공생

문제 출처: https://www.acmicpc.net/problem/1956

풀이

사소한 오타 하나때문에 15번정도 제출오류가 났던 문제입니다.

풀이 방법순으로 적어보면,

1. map을 INF로 초기화해놓는다.

2. 플로이드와샬을 돌려서 map에 각 노드에서 각 노드로 가는 최단거리를 저장한다.

3. 각 노드에서 노드로 가는 길 중 INF가 아닐때만(길이 있을 때만) 사이클의 최단길이를 비교합니다.

4. map[i][j]!=INF&&map[j][i]!=INF이면 사이클이 존재하는 것이고, 결국 temp가 INF라면 사이클이없으므로, -1을출력합니다. 

코드

문제 출처: https://www.acmicpc.net/problem/1389

풀이

문제 조건에맞게 예제를 그려서 보면 문제에서 원하는 답은 어떤정점에서 각 정점으로 가는 최단거리의 합이 가장 작은 정점임을 알 수 있습니다.

문제를 읽어보면 플로이드와샬 알고리즘으로 풀 수 있음을 짐작 할 수 있습니다.

플로이드 와샬 알고리즘으로 풀 때 한 노드에서 다른 노드로 가는 길이 없을 때를 0이아닌 INF로 채워넣고 푸는 방법과 0으로 초기화시켜놓고 푸는

방법이 있는데, 0으로 초기화 시켜서 풀 경우, "길이 없음"과 최단거리의 의미가 충돌되므로 출발->도착 하는 지점이 없을 경우는

일단 map[i][j]를 출발->거치고->도착하는 값으로 설정시켜줘야합니다. 

저는 INF로 채워놓고 풀었습니다.(취향 차이인 것 같습니다.)

main문에서 배열을 INF로 채워넣지않고(0으로해놓고) 플로이드 3중for문내부 의 주석을 해제하면 0으로 놓고 푸는 풀이가 됩니다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int INF =10000000;
int n, m, map[101][101], a, b;
int index = 0;
void floyed();
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			map[i][j] = INF;
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;
	}
	floyed();
	cout << index << '\n';
}
void floyed()
{
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (i == j)continue;
				/*if (map[i][k] && map[k][j])
				{
					if (map[i][j] == 0)
						map[i][j] = map[i][k] + map[k][j];
					else map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
				}*/
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
			}
		}
	}
	int val = 10000000;
	for (int i = 1; i <= n; i++)
	{
		int temp = 0;
		for (int j = 1; j <= n; j++)
		{
			if (i == j)continue;
			temp += map[i][j];
		}
		if (val > temp)
		{
			val = temp;
			index = i;
		}
	}
}

결과

문제출처: https://www.acmicpc.net/problem/2458

풀이

https://www.acmicpc.net/problem/10159 와 거의 동일한 플로이드와샬 알고리즘문제입니다 !

키를 비교할 수 있는 학생의 수는 그 학생보다 키가 작거나 키가 크거나, 이 둘중 하나는 무조건 해당되야합니다.

즉, 비교하고자 하는 학생(X)은 X를 거치는 학생과 X에서 뻗어나가는 학생의 수가 총원이되어야합니다. 

X가 모든학생이 연결되어있어야 한다는것입니다.

X와 연관이없는(x와 이어지는 노드가 없는 경우) 학생이 한명이라도 있다면, 문제의 조건을 어긋나게됩니다.!

코드

#include<iostream>
using namespace std;
int map[501][501];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n, m, a, b;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		map[a][b] = 1;
	}
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (map[i][k] && map[k][j])
					map[i][j] = 1;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= n; j++)
		{
			//본인은 제외하기
			if (i == j)continue;
			//학생->X &&X->학생 루트가 하나라도 없다면
			if (map[i][j] == 0 && map[j][i] == 0)
				//체킹
				cnt++;
		}
		//cnt=0 ? 모두연결되었다 
		//cnt>1 ? 연결되지않은 노드가있다.
		if (cnt == 0)ans++;
	}
	cout << ans<<'\n';
}

결과

문제출처: https://www.acmicpc.net/problem/10159

풀이

대충 그래프 문제이니, 예제를 그래프로그려봅니다. 그리고 보기의 답을 보면, x와 비교할 수없는 물건의 갯수는 x에서 다른 노드로 가는길과 다른 노드에서 x로 가는 길이 없을 때만 해당합니다. 결국, 플로이드와샬로 해결됨을 알 수 있습니다. 

부끄러운 얘기지만, 플로이드 코드를 작성해놓고 카운팅을하는 반복문작성에 시간을 많이 잡아먹었습니다. 헷갈리더라구요. 

플로이드알고리즘이 코드도 직관적이고 이해도 쉬운만큼, 그냥 눈으로만 보고 넘어갈 때가 있었는데 이번에 많이 반성했습니다. 

배운 개념은 꼭 복습을 하는 습관을 가집시다..

코드

#include<iostream>
using namespace std;
int map[101][101];
int main()
{
	int n, m, a, b;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		map[a][b] = 1;
	}
	//플로이드 돌려준다.
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (map[i][k] && map[k][j])map[i][j] = 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (i == j)continue;
			//i에서 j로 가는길도없고, j에서 i로 가는길도 없을때 ++
			if (map[i][j] == 0 && map[j][i] == 0)cnt++;
		}
		cout << cnt << endl;
	}
}

결과

문제출처: https://www.acmicpc.net/problem/11403

풀이

플로이드 와샬 알고리즘은 매우 직관적이고 쉬운 알고리즘으로써, 이 문제에 적용할 수 있습니다.

직관적으로 생각해보면, a=b, b=c 일때 a=c라는 삼단논법의 논리를 이용하자면,

출발하는길->거치는길이 있고, 거치는길에서 도착하는 길이 있으면, 출발하는길->도착하는길이 존재할 수 있습니다. 따라서 이 논리를 플로이드와샬 구현에 그대로 대입하면됩니다.

코드

#include<iostream>
using namespace std;
int map[100][100];
int n;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	//i=거치는길,j=출발,k=도착
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				//출발->거치는길이 있고, 거치는길->도착하는길이있으면
				if (map[j][i] && map[i][k])
					//출발->도착하는길이있다.
					map[j][k] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << map[i][j] << " ";
		}cout << endl;
	}
}

결과