Topcoder SRM436 Div2 FriendScore

1. 문제요약

- 친구의 수 찾기

- 최대 친구를 가진 친구의 수를 출력

- 친구는 직접적으로 아는 친구 A-B

- 친구의 친구 A-B-C

  (영문은 B가 A, C와 친구라면 A는 C와 친구)

  ("2-friend" 라고 나옴)

- vector<string> frineds 가 주어짐 

  친구이면 'Y', 친구가 아니면 'N'

2. 접근방법

3. 시간복잡도

4. 회고

- 일단 친구의 친구의 의미를 잘못 이해함

  A-B-C-D에서 

  A-B-C 이면 A는 C와 친구

  A-C-D 이므로 C는 A와 D 모두 친구이므로 A-D도 친구 인줄 알았음

- 이게 아니라 A-B-C-D 이면 그냥 A는 B, C랑만 친구임

- 플로이드 워셜

  단순히 모든 정점을 방문한다고 생각해서 friends[i][k] == 'Y' && frineds[k][j] == 'Y' 라고 하면

  플로이드에서 0 -(N)-> 0 -(Y)-> 1 인 경우 친구가 아니라고 판단하게 됨

  또한, 0 -(Y)-> 1 -(Y)-> 0 인경우는 friends[0][0] 을 친구로 만들어 버림

  friends 를 업데이트 하게 되면 A-B-C-D 에서 A-D가 친구로 판단 하기 때문에 다른 친구관계를 저장할 다른 배열이 필요함

- 3가지 경우로 나눠야 함

  ⅰ) A -(N)-> A -(Y)-> B 인 경우      

i == k && friends[k][j] == 'Y'

  ⅱ) A -(Y)-> B -(N)-> B 인 경우      

k == j && friends[i][k] == 'Y'

  ⅲ) 일반적인 경우 A -(Y)-> B -(Y)-> C      

friends[i][k] == 'Y' && friends[k][j] == 'Y'

  ※ 나머지 

     0 -(Y)-> 1 -(Y)-> 0 으로 돌아오는 경우는 새로 만들어 주는 배열에서 친구관계를 셀때 빼면됨

  플로이드는 경로가 출발, 도착 보다 뒤에 바뀌기 때문에 책처럼 풀 수 없음

  0 -> 1 -> 2 다음엔 0 -> 1 -> 3 ... 1 -> 1 -> 3 이런 순이기 때문에 한 정점에서 시작하는 모든 친구를 셀 수 없음

- dfs 는 

           1

     0 <  |

           2 - 3

  인 경우에 0 - 1 - 2 순으로 방문하면 정점 2는 방문 했기 때문에 더이상 방문을 하지 못함

  하지만 최단거리(친구 2단계) 에서는 0 - 2 - 3 으로 0과 3이 친구가 될 수 있음

- bfs 는 깊이(친구 2단계)를 지정해주면 풀 수있음

소스코드 : 플로이드

#include<iostream>
#include<string>
#include<vector>
using namespace std;

class FriendScore{
public:
	int highestScore(vector <string> friends){
		int ans = 0; int n = friends[0].size();
		vector<vector<bool> > map(n, vector<bool>(n, false));

		for (int k = 0; k < n; k++)
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					if ((i == k && friends[k][j] == 'Y') || (k == j && friends[i][k] == 'Y') || (friends[i][k] == 'Y' && friends[k][j] == 'Y'))
						map[i][j] = true;
		
		for (int i = 0; i < n; i++){
			int temp = 0;
			for (int j = 0; j < n; j++){
				if (i != j && map[i][j]) temp++;
			}
			if (ans < temp) ans = temp;
		}
		return ans;
	}
};

소스코드 : bfs

#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;

class FriendScore{
public:
	int highestScore(vector <string> friends){
		int ans = 0;
		vector<bool> check;
		queue<pair<int, int> > q;

		for (int i = 0; i < friends[0].size(); i++){
			check = vector<bool>(friends[0].size(), false);
			check[i] = true;
			q.push(make_pair(i, 0));

			int temp = 0;
			while (!q.empty()){
				int now = q.front().first;
				int deep = q.front().second;
				q.pop();

				for (int j = 0; j < friends[0].size(); j++){
					if (deep < 2 && !check[j] && friends[now][j] == 'Y'){
						check[j] = true;
						q.push(make_pair(j, deep + 1));
						temp++;
					}
				}
			}
			if (ans < temp) ans = temp;
		}
		return ans;
	}
};