• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

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;
}

답변 3

·

답변을 작성해보세요.

0

네 맞습니다.  잘 하셨네요:)

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차원으로 만들어 아이디를 매핑해서 하시면 됩니다. 

 

감사합니다. 

Pa_fs님의 프로필

Pa_fs

질문자

2022.05.17

답변 감사합니다. 3주차 치킨배달 문제 보고 이 문제에 적용해보았습니다.

http://boj.kr/8f480e247bf04f5ab84d9a123a49b02f

선생님 의도하신게 맞을까요?

혹시 못 보실까봐 다시 댓글달아요 :)

잘하셨구요. 그렇게 인덱스화 해서 combi 돌려서 조합만들어서 하시는게 맞습니다. 또한

지금 void형으로 만드셨는데 이를 int화 시켜서 하는 연습도 해보세요. 

res = max(res, area);

이렇게 하셨잖아요. 

근데 이걸

res = max(res, calc());

이런식으로 해서 calc는 area를 반환하는 것으로 만들어보세요. 

이렇게 void형으로 해보고 int형으로 해보고 하면서 자유로이 함수를 만드는 연습을 하시면 도움이 됩니다. 나중에요. ㅎ

 

감사합니다.

Pa_fs님의 프로필

Pa_fs

질문자

2022.05.18

네 복습할 때 바꿔가며 해보겠습니다. 감사합니다!!

0

Pa_fs님의 프로필

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로 해놨네요 ㅠㅠ