2-p14502 vector<pair<int,int>>의 조합을 뽑아내는 방법은 없을까요?

작성한 질문수 65

0

안녕하세요 mh님 ㅎㅎ

조합 combi 재귀함수를 통해서 로직을 구축하시려고 한다면

다음과 같이 하시면 됩니다.

#include<bits/stdc++.h>
using namespace std;
int a[10][10], visited[10][10], n, m, ret;
vector<pair<int, int>> virusList, wallList;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int walllen;
void dfs(int y, int x){
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx] || a[ny][nx] == 1) continue;
        visited[ny][nx] = 1;
        dfs(ny, nx);
    }
    return;
}
int solve(){
    fill(&visited[0][0], &visited[0][0] + 10 * 10, 0); 
    for(pair<int, int> b : virusList){
        visited[b.first][b.second] = 1;
        dfs(b.first, b.second);
    } 

    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 0 && !visited[i][j])cnt++;
        }
    } 
    return cnt;  
}
void combi(int start, vector<int> b){ 
    if(b.size() == 3){  
		a[wallList[b[0]].first][wallList[b[0]].second] = 1;
		a[wallList[b[1]].first][wallList[b[1]].second] = 1;
		a[wallList[b[2]].first][wallList[b[2]].second] = 1;
		ret = max(ret, solve());
		a[wallList[b[0]].first][wallList[b[0]].second] = 0;
		a[wallList[b[1]].first][wallList[b[1]].second] = 0;
		a[wallList[b[2]].first][wallList[b[2]].second] = 0;  
        return;
    }
    for(int i = start + 1; i < walllen; i++){
        b.push_back(i);
        combi(i, b);
        b.pop_back();
    }
    return;
}  

int main(){
    cin >> n >> m;
    for(int i = 0; i <n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
            if(a[i][j] == 2) virusList.push_back({i, j});
            if(a[i][j] == 0) wallList.push_back({i, j});
        }
    }
	walllen = wallList.size();
	vector<int> b;
	combi(-1, b); 
    cout << ret << "\n";
    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.