백준 1043 거짓말

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

문제 요약

1. 입력 첫째 줄에 사람 수 N, 파티의 수 M이 주어진다.
2. 지민이는 파티에서 거짓말을 할 예정이다.
3. 그러나 지민이의 진실을 아는 사람이 입력 둘째 줄에 사람수와 번호로 주어진다.
4. 입력 3째줄 부터 파티 참여 인원 수와 해당 인원의 번호가 주어진다.
5. 따라서 진실을 아는 사람이 오는 파티에서는 거짓말을 할 수 없다.
6. 출력은 지민이가 거짓말을 할 수 있는 파티의 개수

풀이

1. 3번째 줄부터 주어지는 파티 참여 인원들간의 관계를 bool 타입으로 정리한다.
   즉, i,j가 같은 파티에서 본 사람의 경우 v[i][j] = true와 같은 관계를 정리한다.
2. 입력 2번째 줄에 주어진 진실을 아는 사람들을 한번씩 bfs로 그래프 탐색을 진행한다.
   이렇게 하고 나면 진실을 아는 사람과 이 사람들과 같은 파티에 참석한 사람들을 골라낼 수 있다.
3. 마지막으로 파티 참여 정보를 탐색하면서 2번에 해당하지 않는 사람들로만 구성된 파티의 개수를 count해준다.

코드

//전역 변수로 선언
int N, M; 
vector<int> truth; // 진실을 아는 사람들을 담은 container
bool connection[52][52]; // 파티 참여인원, 진실을 아는 사람들의 관계
bool v[52];// bfs를 위한 visited
vector<vector<int>> party; // party  참여 인원의 정보

// BFS 함수
void bfs(int index) {
	queue<int> q;
	q.push(index);
	v[index] = true;
    
	while (!q.empty()) {
		auto t = q.front();
		q.pop();
        
		for (int i = 1; i <= N; i++) {
			if (connection[t][i]) {
				if (v[i]) continue;
				q.push(i);
				v[i] = true;
			}
		}
	}
}

void input() {
	cin >> N >> M;
	int truchCnt, temp;
	cin >> truchCnt;
    
	while (truchCnt--) {
		cin >> temp;
		truth.push_back(temp);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	
    
	int temp, res = 0;
    
	input();
    
	for (int i = 0; i < M; i++) {
		cin >> temp;
		int t;
		vector<int> p;
        
		while (temp--) {
			cin >> t;
			p.push_back(t);
		}
        
		party.push_back(p);
        
		for (int i = 0; i < p.size() - 1; i++) {
			for (int j = i + 1; j < p.size(); j++) {
				connection[p[i]][p[j]] = true;
				connection[p[j]][p[i]] = true;
			}
		}
	}
    
	for (auto t : truth) {
		bfs(t);
	}
    
	for (auto t : party) {
		bool check = false;
        
		for (auto tt : t) {
			if (v[tt]) {
				check = true;
				break;
			}
		}
        
		if (check == false) {
			res++;
		}
	}
    
	cout << res;
	return 0;
}

후기

1. 동적으로 connection을 구성하는 부분 보강해보자
2. method 별로 나누어서 함수화하자
3. 가독성이 좋은 코드, 변수 이름을 생각해서 지어주자