인프런 커뮤니티 질문&답변

안녕하세요 준서님ㅎㅎ

combi 함수가 이상한 것 같습니다.

예를 들어

3 3

0 0 0

0 0 0

0 0 2

이렇게 입력을 했을 때 모든 경우의수를 확인할 수 있을까요?

디버깅코드는 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;

int n, m;
int arr[8][8];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
int visited[8][8];
int res = -1;
int twos = 0;
int zeros;

int dfs(int row, int col) {
	visited[row][col] = 1;
	int cnt = 1;
	for (int i = 0; i < 4; i++) {
		int nrow = row + dy[i];
		int ncol = col + dx[i];
		if (nrow < 0 || nrow >= n || ncol < 0 || ncol >= m) {
			continue;
		}
		if ((arr[nrow][ncol] == 0 || arr[nrow][ncol] == 2)
			&& !visited[nrow][ncol]) {
			cnt += dfs(nrow, ncol);
		}
	}
	return cnt;
}

void combi(int start, vector<pair<int, int>>& v) {
	if(v.size() >= 3) {
		int max = 0;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				visited[i][j] = 0;
			}
		}

		for (auto& it : v) {
			arr[it.first][it.second] = 1;
            cout << it.first << " : " << it.second << " // ";
		} 
        cout << "\nCLEAR\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 2 && visited[i][j] == 0) {
					int temp = dfs(i, j);
					max += temp;
				}
			}
		}

		if (zeros + twos - max > res) {
			res = zeros + twos - max;
		}
		for (auto& it : v) {
			arr[it.first][it.second] = 0;
		}
		return;
	}
	int row = 0, col = 0;
	if(start != 0){
		row = start / m;
		col = start % m;
	}

	for (int i = row; i < n; i++) {
		for (int j = col ; j < m; j++) {
			if (arr[i][j] == 0) {
				v.push_back(make_pair(i, j));
				combi(start + 1, v);
				v.pop_back();
			}
		}
	}
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 0) {
				zeros++;
			}
			else if (arr[i][j] == 2) {
				twos++;
			}
		}
	}

	zeros = zeros - 3;
	vector<pair<int, int>> v;
	combi(0, v);
	cout << res;

	return 0;
}

이렇게 했을 때

일부를 보시면

3 3
0 0 0
0 0 0
0 0 2
0 : 0 // 0 : 1 // 0 : 2 //
CLEAR
0 : 0 // 0 : 1 // 1 : 2 //
CLEAR
0 : 0 // 0 : 2 // 0 : 2 //
CLEAR
0 : 0 // 0 : 2 // 1 : 2 //
CLEAR
0 : 0 // 1 : 1 // 0 : 2 //
CLEAR
0 : 0 // 1 : 1 // 1 : 2 //
CLEAR
0 : 0 // 1 : 2 // 0 : 2 //
CLEAR
0 : 0 // 1 : 2 // 1 : 2 //
CLEAR
0 : 0 // 2 : 1 // 0 : 2 //
CLEAR
0 : 0 // 2 : 1 // 1 : 2 //

앞의 출력결과처럼 모든 경우의 수가 출력 되지 않는 것을 볼 수 있습니다.

(0, 0) 포함한 경우의 수 전부가 출력이 안됩니다.

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

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

감사합니다.

강사 큰돌 올림.