백준 스터디 9주차 - 발표

Q1. 5597 과제 안내신 분..?

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	bool check[31];
    memset(check, 0, sizeof(check));

	for (int i = 0; i < 28; i++) {
		int num;
		cin >> num;
		check[num] = true;
	}

	for (int i = 1; i < 31; i++) {
		if(!check[i]) cout << i << '\n';
	}

}

수가 입력되었는지 저장할 배열 check를 선언한 후 false로 모두 초기화한다.
이후 28개의 수를 입력 받으면서, 해당 수의 값을 index로 갖는 배열 값을 true로 변경한다.
그리고 for문을 이용해 값이 false인 배열 부분의 index 값을 출력한다.

---

Q2. 2668 숫자 고르기

먼저 두 배열에서 같은 인덱스 값을 가지는 값들을 연결해 그래프로 만들어 보면,

문제의 답이 되는 1,3,5는 사이클을 형성하고 있다는 공통점을 확인할 수 있었다.

그래서 그래프 탐색을 통해 싸이클이 존재하는 지를 확인하고, 사이클을 이루는 원소들은 result 배열에 값을 추가하는 방식으로 코드를 구현했다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int arr[101] = { 0 };
int visited[101] = { 0 };
vector<int> result;

void dfs(int current, int start) {
	if (visited[current]) {
		if (current == start) {
			result.push_back(start);
		}
	}
	else {
		visited[current] = 1;
		dfs(arr[current], start);
	}
}

int main() {

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
		

	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		dfs(i, i);
	}

	// 결과 출력
	cout << result.size() << endl;
	sort(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << endl;

}

먼저 배열에 값들을 입력받고 방문을 체크할 배열을 모두 false로 초기화한다.
이후 dfs를 시행하는데, 이 때 어디서부터 탐색을 진행했는 지 알도록 start 변수도 매개변수로 계속 함께 넘겨준다.
이미 방문한 노드에 다시 방문하게 됐는데 현재 노드 값과 시작 노드 값이 같으면 사이클이 만들어진 경우이므로, 해당 시작 노드의 값은 결과 집합의 값이 될 수 있다.
그렇게 확인 된 값을 결과가 될 집합에 수를 추가하고, 이 과정을 모든 원소에 대해 반복한 후 result 벡터를 정렬하여 벡터의 크기와 원소들을 출력한다.