2-P 2차원배열에서 조합 재귀 질문있습니다
1200
3 asked
연구소 문제에서 조합을 재귀함수로 뽑고싶은데 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;
}
Answer 3
0
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차원으로 만들어 아이디를 매핑해서 하시면 됩니다.
감사합니다.
0
답변 감사합니다. 3주차 치킨배달 문제 보고 이 문제에 적용해보았습니다.
http://boj.kr/8f480e247bf04f5ab84d9a123a49b02f
선생님 의도하신게 맞을까요?
0
혹시 못 보실까봐 다시 댓글달아요 :)
잘하셨구요. 그렇게 인덱스화 해서 combi 돌려서 조합만들어서 하시는게 맞습니다. 또한
지금 void형으로 만드셨는데 이를 int화 시켜서 하는 연습도 해보세요.
res = max(res, area);
이렇게 하셨잖아요.
근데 이걸
res = max(res, calc());
이런식으로 해서 calc는 area를 반환하는 것으로 만들어보세요.
이렇게 void형으로 해보고 int형으로 해보고 하면서 자유로이 함수를 만드는 연습을 하시면 도움이 됩니다. 나중에요. ㅎ
감사합니다.
0
미리 자답합니다.
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로 해놨네요 ㅠㅠ
1-E질문입니다!
0
509
2
3-L 틀린 부분 피드백 부탁드립니다.
0
811
2
1-A문제 순열재귀함수 질문입니다.
0
376
1
1-A 일곱난쟁이문제입니다
0
451
1
문제 풀 때 방향성에 대해
0
793
1
맥에서 vs code로 실행 관련 질문입니다
0
515
1
17071번 메모리 초과
0
381
1
1-C질문입니다!
0
412
2
2-B BFS 시간초과질문
0
623
2
1-O 13번 라인
0
435
1
6-J 놀이공원 문제 질문
0
376
1
구현관련 질문
0
479
1
강의 교안
0
313
1
실력을 더 올리고나서 강의를 보는 것이 맞을까요?
0
541
1
안녕하세요! 재귀함수에 관해서 질문드립니다
0
531
1
1-K
0
468
2
3-G번 질문있습니다.
1
464
3
3-C 실행 시간 질문드립니다.
0
489
1
4-A 문제 풀이 질문있습니다.
0
586
2
비트마스킹 연산자 "1의 보수" 영문 표기법
0
430
1
격자탐색 문제에서 BFS 시간복잡도 질문드립니다.
0
329
1
3-O go 함수 질문 드립니다.
1
437
2
4-A 출력 질문
0
299
1
1주차 1-O 질문드립니다
0
250
1

