기록을

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

R G B 각각으로 이루어진 영역의 개수를 찾으면 되는 문제였다.

추가적인 경우는 R과 G를 같게 보고 위의 작업을 반복해주면 된다.

첫 번째 경우를 처리한 이후에 R성분을 G로 바꿔서 같은 작업을 반복했다.

주의할 사항은 입력을 받는 것이다. m을 이차원 char 배열로 잡아두고, string으로 한 줄씩 입력을 받았다.

#pragma warning(disable:4996)
#include<iostream>
using namespace std;
char m[101][101];
bool vis[101][101];
int N;
int dr[4] = { 0,0,1, -1 };
int dc[4] = { 1,-1,0,0 };
int cnt1 = 0, cnt2 = 0;
bool norCheck(int nr, int nc, char c) {
	if (nr < 0 || nc < 0 || nr >= N || nc >= N || vis[nr][nc] || m[nr][nc] != c)
		return true;
	else
		return false;
}

void dfs(int row, int col, char c) {
	vis[row][col] = true;
	
	for (int i = 0; i < 4; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];

		if (norCheck(nr, nc, c)) continue;
		dfs(nr, nc, c);
	}
}
int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> m[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!vis[i][j]) {
				dfs(i, j, m[i][j]);
				cnt1++;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (m[i][j] == 'R') m[i][j] = 'G';
			vis[i][j] = false;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!vis[i][j]) {
				dfs(i, j, m[i][j]);
				cnt2++;
			}
		}
	}
	cout << cnt1 << ' ' << cnt2 << '\n';

	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/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인 경우)인 것이다.