알고리즘

[boj4963, boj15652/c++] 섬의 개수, N과 M(4)

IT 참다랑어 2023. 5. 2. 23:12

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

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

dfs 로 해결. 대각선도 탐색 가능.

#include <iostream>
#include <vector>

using namespace std;

int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

int** map;
int** visited;
int w, h;

void dfs(int y, int x) {
	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= w || ny >= h) continue;
		if (!visited[ny][nx] && map[ny][nx]) {
			visited[ny][nx] = 1;
			dfs(ny, nx);
		}
	}
}

int solve(int w, int h) {
	map = new int* [h];
	visited = new int* [h];
	int ret = 0;
	for (int i = 0; i < h; i++) {
		map[i] = new int[w];
		visited[i] = new int[w];
	}
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> map[i][j];
			visited[i][j] = 0;
		}
	}
	
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (!visited[i][j] && map[i][j]) {
				visited[i][j] = 1;
				dfs(i, j);
				ret++;
			}
		}
	}

	delete[] map;
	delete[] visited;
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	while (1) {
		cin >> w >> h;
		if (!w&& !h) break;
		cout << solve(w, h) << '\n';
	}
	return 0;
}

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

 

15652번: N과 M (4)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

이 문제도 dfs를 이용해서 푸는 문제라 같이 업로드

#include <iostream>

using namespace std;

int N, M;
int* arr;
int* visited;

void dfs(int num, int depth) {
	if (depth == M) {
		for (int i = 0; i < M; i++) {
			cout << visited[i] << ' ';
		}
		cout << '\n';
		return;
	}

	for (int i = num; i < N; i++) {
		visited[depth] = arr[i];
		dfs(i, depth + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	arr = new int[N];
	visited = new int[M];
	for (int i = 0; i < N; i++) {
		arr[i] = i + 1;
	}

	dfs(0, 0);
}

'알고리즘' 카테고리의 다른 글

[boj2599/c++] 짝 정하기  (1) 2023.05.05
[boj11728/c++] 배열 합치기  (0) 2023.05.04
[boj9934/c++] 완전 이진 트리  (0) 2023.05.01
[boj1389/c++] 케빈 베이컨의 6단계 법칙  (0) 2023.05.01
[boj1874/c++] 스택 수열  (0) 2023.04.27