https://www.acmicpc.net/problem/4963
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
이 문제도 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 |