백준 1765 : 닭싸움 팀 정하기 C++

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

1765번: 닭싸움 팀 정하기

 

풀이

1. 처음 입력을 받을때 그래프 연결하듯이 입력받는다.

 

2. visited를 관리하는데, 여기서 visited란 방문했다라는 표현보다는, 특정 팀에 속해있다로 이해하는게 맞다

 -> 따라서 처음 루프를 확인할때 visited가 1이면 answer를 올리지 않는다. 이미 팀에 속해있고, 이 팀에 추가 멤버를 영입하는 과정이기 때문

 

3. 루프

 1) visited가 1이면 answer는 올리지 않음

 

 2) 내 친구면 우리팀으로 영입

 -> 이미 영입 되어있어도 answer에 영향을 주지 않기 떄문에 추가 처리를 하지 않았다.

 

 3) 내 원수면, 그 원수들도 내 팀으로 영입

if (v[v[i][j].second][k].second == i)
   continue;

 -> 사실 아래과정을 할 필요는 없다, 주석처리해도 정답 처리됨

* 실제 업무에서는 이렇게 '결과론적으로는 똑같이 작동한다' 라고 그냥 넘어가면 크으은일 난다.

 다른 함수에서 가져오는 변수도 워낙 많고, RTOS의 경우 중간에 변수 갑이 뻑나는 경우도 굉장히 많기때문. 

항상 예외 처리, 각 TC에 대한 대처를 모두 해놔야 된다.

 

물론 코테에서는 정답이면 장떙

 

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

// 내 친구의 친구는 친구
// 원수의 원수는 친구
// 같은 팀에 있는 사람들은 몽땅 친구
// 가장 많은 팀이 만들어지려면?

int n, m;
vector<pair<char, int> > v[1001];
int visited[1001] = { 0, };

int main()
{
	int answer = 0;
	cin >> n;
	cin >> m;


	for (int i = 0; i < m; i++)
	{
		char tmp1;
		int tmp2, tmp3;
		cin >> tmp1 >> tmp2 >> tmp3;

		v[tmp2].push_back(make_pair(tmp1, tmp3));
		v[tmp3].push_back(make_pair(tmp1, tmp2));
	}

	for (int i = 1; i <= n; i++)
	{
		if (visited[i] != 1)
			answer++;
		visited[i] = 1;
		for (int j = 0; j < v[i].size(); j++)
		{
			// 내 친구면 우리팀ㅇ 포함
			if (v[i][j].first == 'F')
			{
				visited[v[i][j].second] = 1;
			}
			else
			{
				// 원수면 걔의 원수들을 다 내팀으로 흡수
				for (int k = 0; k < v[v[i][j].second].size(); k++)
				{
					if (v[v[i][j].second][k].second == i)
						continue;
					if (v[v[i][j].second][k].first == 'E')
					{
						visited[v[v[i][j].second][k].second] = 1;
					}
				}
			}
		}
	}
	cout << answer << endl;

	return 0;
}