[C++/17089] 세친구

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

일단 이 문제는 이해부터 해야된다. 

A친구가 있고 B 친구가 있는데 A와 B는 친구 사이다. 이러면 이차원 배열 또는 벡터를 이용해서 친구 사이를 만들어 줄 수 있고, 그런데 여기서 총 친구들 중에서 세 사람을 골라서 서로를 제외하고 친구 수가 가장 적은 친구 그룹을 구해야한다.

그렇다면, 이차원 배열을 이용해서 친구 사이를 유지하면 됩니다. 그리고 친구의 친구가 아니고 셋이 전부 친구여야 한다는 조건을 갖고 있다. 그리고 이러한 조건을 이용해서 전체 인원중 세명을 전부 찾아보면 된다.

사람의 수는 4000명이고, 4000 * 4000 * 4000은? 64,000,000,000이 나와서 시간상 처리를 할 수 없을것 같지만? 우리에게는 친구사이를 유지하는 조건을 갖고있다. 특히 세명이 전부 친구여야한다.

이것은 정말로 이해가 가지않았는데, 그리고 나는 4000 ^ 3이 작은 값인줄 알았는데, 질문 게시판을 보고 깨달았다. 내가 잘못풀었는데 어떻게 맞췄지? 

즉 이러하다, 처음 A와 B는 전부 비교를한다. N^2의 시간 복잡도를 갖게 된다. 그리고 우리는 조건이 존재한다. A와 B 사이에 친구라면? 그렇다면 만약 M개의 전부가 친구라고 가정한다면? 총 M개가 된다. 즉 N^2일 지라도 조건에 따라서 최대 M개까지만 세번째 for문을 돌게 된다는 것이다. 그리고 그런 경우의 수를 이어서 N번을 전부 살펴보게 된다. 그렇다면?

N^2와 + MN이 된다.  O((N + M)N)이 되어버리는 것인데. 그렇다면? 8000 * 4000이 되므로 32,000,000이 되어 문제를 해결할 수 있게 된다. 아주 의미있는 문제였다. 아래는 정답코드이다.

#include<iostream>

#define MAX 4010
using namespace std;

int ans = -1,n,m,chk[MAX][MAX],friends[MAX];

void init() {
	
	cin >> n >> m;
	
	for(int i = 0; i < m; i++){
		int from,to; cin >> from >> to;
		
		friends[from] += 1;
		friends[to] += 1;
		chk[from][to] = 1;
		chk[to][from] = 1;
	}
	
}

void solve() {
	
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			if(chk[i][j]){
				for(int k = j + 1; k <= n; k++){
					if(chk[i][k] && chk[j][k]){
						int sum = friends[i] + friends[j] + friends[k] - 6;
						if(ans == -1 || ans > sum) ans = sum;
					}
				}
			}
		}
	}
	
}


int main() {
	
	init();
	solve();
	cout << ans;
	
	return 0;
}