-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
2-P 2차원배열에서 조합 재귀 질문있습니다
22.05.16 18:40 작성 조회수 940
0
연구소 문제에서 조합을 재귀함수로 뽑고싶은데 2차원배열에서 조합뽑는 방법을 잘 모르겠습니다.
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0 ,-1 };
int n, m, res;
int c_n, c_r = 3, cnt = 0; // 조합(재귀)에 쓰이는 변수
int map[9][9], visited[9][9];
void DFS(int y, int x) {
if (map[y][x] == 1 || visited[y][x]) return;
visited[y][x] = 1;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
if(map[ny][nx] == 0 && visited[ny][nx] == 0) DFS(ny, nx);
}
}
void build(int start) {
if (cnt == c_r) {
memset(visited, 0, size(visited));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 2) DFS(i, j);
}
}
int area = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] == 0 && map[i][j] == 0) area++;
}
}
res = max(res, area);
}
else {
for (int i = start + 1; i < c_n; i++) {
int y = i / m;
int x = i % m;
cnt++;
map[y][x] = 1;
build(i + 1);
map[y][x] = 0;
cnt--;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
}
}
c_n = n * m; // 조합 n*m개 중 뽑기
build(-1);
cout << res;
return 0;
}
답변을 작성해보세요.
0
0
큰돌
지식공유자2022.05.17
2차원배열을 재귀로 뽑는 것은 간단합니다.
2차원 배열을 1차원배열로 만들어 놓고 그걸 기반으로 제가 교안에서 설명드린 조합 재귀함수를 쓰면 되는 것이죠.
예를 들어
1 2 3
4 5 6
이라는 2 * 3 배열이 있다고 해봅시다.
여기서 1 2 3 4 5 6 이라는 id를 부여할 수 있겠죠? 그러면 이 6개의 아이디를 기반으로 2개를 뽑는 조합함수를 짜면
1, 2,
1, 3
...
이런 식으로 나옵니다.
이런식으로 하시면 됩니다. 3차원도 똑같이 1차원으로 만들어 아이디를 매핑해서 하시면 됩니다.
감사합니다.
Pa_fs
질문자2022.05.17
답변 감사합니다. 3주차 치킨배달 문제 보고 이 문제에 적용해보았습니다.
http://boj.kr/8f480e247bf04f5ab84d9a123a49b02f
선생님 의도하신게 맞을까요?
큰돌
지식공유자2022.05.17
혹시 못 보실까봐 다시 댓글달아요 :)
잘하셨구요. 그렇게 인덱스화 해서 combi 돌려서 조합만들어서 하시는게 맞습니다. 또한
지금 void형으로 만드셨는데 이를 int화 시켜서 하는 연습도 해보세요.
res = max(res, area);
이렇게 하셨잖아요.
근데 이걸
res = max(res, calc());
이런식으로 해서 calc는 area를 반환하는 것으로 만들어보세요.
이렇게 void형으로 해보고 int형으로 해보고 하면서 자유로이 함수를 만드는 연습을 하시면 도움이 됩니다. 나중에요. ㅎ
감사합니다.
0
Pa_fs
질문자2022.05.16
미리 자답합니다.
1.
재귀 들어가기 전에 map[y][x]가 0인 경우를 체크 안했네요
그래도 틀리네요..
cnt++;
map[y][x] = 1;
build(i + 1);
map[y][x] = 0;
cnt--;
2.
memset(visited, 0, size(visited));
sizeof로 해야되는데 size로 해놨네요 ㅠㅠ
답변 3