[백준] #9466 텀 프로젝트

👋 백준 9466번 풀이 코드 (TIL 231213)

메모리 초과 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

vector<pair<int,int>> team;
queue<pair<int,int>> pick;

void checking_team() {
	int start;
	int result = 0;

	for (int i = 0; i < team.size(); i++) {
		if (team[i].second < 0) continue;
		else if (team[team[i].second].second < 0) { //이미 팀을 이루었거나, 더 이상 팀을 못이루는 경우
			team[i].second = -2;
			continue;
		}
		else {
			start = team[i].first;
			pick.push(team[i]);
			
			while (pick.back().second != start) {
				if (pick.back().second == -1) {
					while (!pick.empty()) pick.pop();
					break;
				}
				pick.push(team[pick.back().second]);
			}
			
			while (!pick.empty()) {
				team[pick.front().first].second = -1;
				pick.pop();
			}

			if (team[i].second >= 0 ) team[i].second = -2;
		}
		
	}

	for (int i = 0; i < team.size(); i++) {
		//cout << team[i].first << '/' << team[i].second << ' ';
		if (team[i].second == -2) result++;
	}
	cout << result;
	cout << '\n';
}

int main() {
	int tc, temp, students_num;
	cin >> tc; //test case 개수

	for (int i = 0; i < tc; i++) {
		cin >> students_num; //학생수
		for (int j = 0; j < students_num; j++) {
			cin >> temp;
			if (j == temp - 1) team.push_back(make_pair(j, -1));
			else team.push_back(make_pair(j, temp - 1));
		}
		checking_team();
		team.clear();
	}

	return 0;
}

문제점

• 학생의 number는 1부터 시작하고, 배열의 index는 0부터 시작하니까 학생의 number를 사용하기 위해 일부러 pair를 사용하여 본인의 number와 원하는 학생의 number를 저장했다.
  그러다보니 코드에서도 first, second를 사용하느라 가독성이 떨어지고 복잡해졌다.
  -> 그냥 MAX값을 지정 후 배열을 선언 및 초기화 want[MAX] = {0, }
  -> index 1부터 원하는 값을 저장! (이리도 간단한 걸...)

• 굳이 쓸데 없는 queue를 사용하여 초기화에서 복잡해졌다.

• 방문했다는 것을 확인하기 위해서 따로 visited배열을 두지 않고, 굳이 second의 값을 바꿨다.

• 사이클이 완성된다는 것을 확인하는 방법을 구현을 제대로 하지 못했다.

수정 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h> //memset함수
#define MAX 100001

using namespace std;

int want[MAX] = { 0, };
bool visited[MAX] = { 0, };
bool done[MAX] = { 0, };

int members_num = 0;

void dfs(int current_student) {
	int next_student = want[current_student];
	visited[current_student] = 1;
	if (!visited[next_student]) dfs(next_student);
	else {
		if (!done[next_student]) { //방문은 되었으나, 팀 결정이 안된 경우 -> 사이클이 만들어짐
			for (int i = next_student; i != current_student; i = want[i]) members_num++;
			members_num++;
		}
	}
	done[current_student] = 1;
}

int main() {
	int tc, students_num;
	cin >> tc; //test case 개수

	for (int i = 0; i < tc; i++) {

		//사용배열 초기화
		memset(want, 0, sizeof(want));
		memset(visited, 0, sizeof(visited));
		memset(done, 0, sizeof(done));

		cin >> students_num; //학생수

		for (int j = 1; j <= students_num; j++) { //학생의 number는 1부터 시작이므로 j값을 1부터로 설정
			cin >> want[j];
		}

		members_num = 0; //결과값 초기화

		for (int j = 1; j <= students_num; j++) { //방문되지 않은 학생들에 대해 dfs
			if (!visited[j]) dfs(j);
		}
		cout << students_num - members_num << '\n';
		
	}

	return 0;
}

수정 사항

• want, visited, done 배열을 각각 두어 팀을 원하는 학생 number, 방문 여부, 팀 구성 여부를 각각 저장하여 사용하였다.
• main 함수 내에서 방문되지 않은 학생에 대해서만 dfs 함수를 호출하였다.
• 사이클에 포함되어 있는 학생을 확인하기 위해 재귀를 사용하지 않고, 반복문을 사용하였다.

for (int i = next_student; i != current_student; i = want[i]) members_num++;