기록을

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

숫자를 중복해서 뽑을 수 있기 때문에 숫자의 사용 여부를 관리하는 배열이 필요가 없다.

num배열에 사용할 수 있는 수들을 입력받고 정렬해준다.

#include<iostream>
#include<algorithm>
using namespace std;
int N, M, num[8], arr[8];

void func(int k) {
	if (k == M + 1) {
		for (int i = 1; i <= M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= N; i++) {
		arr[k] = num[i]; //k번째 자리로 i번째 숫자 선택
		func(k + 1); //k+1번째 자리 정하기
	}
}
int main(void) {
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> num[i];
	sort(num + 1, num + N + 1); //수열이 오름차순으로 나오게 하기 위해 오름차순 정렬
	func(1); //1번째 자리를 선택할 차례

	return 0;
}

큐를 활용한 BFS 풀이가 궁금하다면 아래 글을 참고하기 바란다.

 https://hugssy.tistory.com/56?category=843457

평소 무의식적으로 bfs로만 풀이를 진행한 것 같아서, 이렇게 가끔 bfs로 풀이했던 문제들을 DFS로 풀이해보려고 한다.

확실히 코드가 간결해지긴 하는 것 같다. 무리 없이 재귀를 따라갈 수 있다면 쉽게 사용할 수 있을 것 같다.

일단 큐 따위를 사용하지 않기 때문에 pair 자료구조도 사용할 필요 없이 그냥 dfs 함수의 인자로는 row 값과 col 값을 담으면 되겠다.

방문한 적 없는 지점이면서 집이 있는 지점에서 최초로 dfs를 시작한다. 즉 main 함수에서 dfs를 실행시키는 것이, 새로운 단지를 찾았다는 것이 되겠다. 따라서 main 함수에서 dfs를 몇 번 수행하는지를 계산하면 단지의 전체 수를 찾을 수 있겠다.

필자는 이것을 벡터로 처리했다. 벡터를 사용하면 단지의 개수가 총 몇 개 나올 것인지 생각할 필요가 없기 때문에 좀 더 편하고 빠르게 문제를 풀 수 있다.

dfs 함수 내에서는, 범위 조건을 만족하고, 방문할 가치가 있는 곳이라면 이어서 dfs를 수행한다.

이어서 dfs를 실행할 상황이 온다는 것은, 곧 집을 하나 더 찾았다는 것을 의미한다.

이때 처음 dfs를 수행하기 시작한 곳도 집이라는 것을 생각해서 homeCnt를 1로 초기화해줘야 한다.

main 함수에서 한 번의 dfs가 모두 끝났다는 것은 단지 하나를 전부 돌았다는 것이다.

따라서 이 타이밍에 집의 개수를 추가해주고 다시 집의 개수를 초기화해주면 되겠다.

#pragma warning(disable :4996)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, m[26][26];
bool vis[26][26];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int homeCnt = 1;
vector<int> v;
void dfs(int row, int col) {
	vis[row][col] = true;

	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];

		if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
		if (vis[nr][nc] || m[nr][nc] == 0) continue;
		
		homeCnt++;
		dfs(nr, nc);
	}
}

int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%1d", &m[i][j]);
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!vis[i][j] && m[i][j] == 1) {
				dfs(i, j);
				v.push_back(homeCnt);
				homeCnt = 1;
			}
		}
	}
	sort(v.begin(), v.end());

	cout << v.size() << '\n';
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << '\n';
	return 0;
}

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

문제 설명

방문 처리가 되지 않은 지점이면서 집인 경우에 bfs를 수행해준다.

한 번 수행할 때마다 단지를 하나씩 찾게 되므로, bfs 함수가 실행될 때 단지의 수를 증가시킨다.

이어서 각 단지마다 집의 개수를 파악해야 한다.

이는 bfs를 수행하면서 큐에 push 되는 횟수를 저장해주면 된다. 당연하게도 집인 경우에만 다음에 이어서 탐색을 하도록 구현했으니까.

주의할 것은, 시작지점 즉 bfs를 시작하는 지점도 집이라는 사실이다. 따라서 단지 내 집의 개수를 저장하는 변수인 homeCnt를 1로 초기화했다.

그리고 초기에는 단지 전체의 수를 저장할 변수도 있었는데, 벡터를 사용하게 되면 벡터의 크기가 곧 단지의 개수가 될 것이기 때문에 이것으로 대신했다.

문제 링크이다.

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

사이클을 탐색할 수 있으면 해결할 수 있는 문제이다.

팀이 결정되는 조건이 결국 사이클을 이루는 조건이기 때문이다.

사이클을 검사할 때 템플릿처럼 활용할 수 있을 것 같다.

먼저 방문처리 배열을 두 개를 둔다.

vis배열은 0인 경우 아예 방문을 하지 않은 것이고, -1인 경우에는 방문을 했고, 더 이상 방문할 필요가 없다는 것이다.

1인 경우에는 현재 방문 중이라는 의미이다.

Done배열은 사이클을 이루는 성분인지 여부를 저장한다.

만약 학생 x를 한번 방문해서 vis[x]가 1인 상태라고 해보자. 즉 방문하고 있는 중이라는 것인데,

이 상태에서 x를 누군가가 또 방문한다는 것은? 학생 1을 포함하는 사이클이 존재한다는 의미이다.

따라서 x는 사이클이라는 것이 확실하기 때문에 done[x]를 true로 설정해준다.

그리고 cycle 검사를 마치면 (재귀를 탈출하면) 더 이상 방문할 필요가 없다는 의미이기 때문에 vis[x]를 -1로 만들어준다.

결과적으로 cycle검사의 탈출 조건은 이미 방문할 필요가 없는 곳이거나(vis가 -1인 경우)

이미 사이클을 이루고 있는 경우(Done이 1인 경우)인 것이다.

문제 링크는 다음과 같다.

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

수열에 오름차순이라는 조건이 존재하기 때문에 수열을 만들기 전에 입력받은 수들을 오름차순 정렬해준다.

또한 증가수열로 나타내야 하기 때문에 특정 자리의 숫자로는, 이 전 자리의 숫자보다 큰 숫자만 올 수 있다.

즉 길이 3인 수열을 만들어야 하는데, 첫 번째 숫자를 3으로 정해놨다고 하자.

3 _ _

이런 상태인데, 2번째 자리에 올 수 있는 숫자는 3보다 큰 숫자라는 뜻이다.

따라서 arr[k - 1] < num[i] 이 조건을 추가해서 구현해주면 된다.

물론 다음 재귀로 들어가기 전에 전역변수를 둬서 i를 저장해두거나, 재귀 함수의 인자로 몇 번째 index의 숫자를 사용했는지 관리해주는 방법도 있다.

func(1)은 이제 첫번째 자리의 숫자를 정해야 한다는 의미이다.

따라서 base condition은 이제 M+1번째 자리의 숫자를 정할 타이밍 일 것이다. 이때가 M번째 숫자까지 결정되었다는 의미이기 때문이다.

#include<iostream>
#include<algorithm>
using namespace std;
int N, M, num[10], arr[10];
bool isused[10];
void func(int k) {
	if (k == M + 1) {
		for (int i = 1; i <= M; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}
	
	for (int i = 1; i <= N; i++) {
		if (!isused[i] && num[i] > arr[k - 1]) {
			arr[k] = num[i];
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> num[i];
	sort(num + 1, num + N + 1);
	
	func(1);
	return 0;
}