2-p14502 질문입니다

Question

안녕하세요 선생님 벽을 3개를 세우라고 해서 조합을 먼저 떠올렸고 영역을 구해야 한다는 부분에서 dfs를 떠올렸습니다 그래서 조합과 dfs를 사용해 벽을 3개 세울때마다 dfs 및 visited배열을 매번 초기화 해주고 2차원 배열 arr을 돌면서 2(바이러스)가 나올때마다 동서남북으로 0또는 2인 곳으로 탐색해가며 영역의 크기를 구하게 해주었습니다. 예제는 분명히 다 맞는데 틀리는 이유가 뭘까요? 0또는 2로 한게 잘못된 걸까요? http://boj.kr/5d0f072fce1a471fb02deec85b4d906d

큰돌 · Answer

안녕하세요 준서님ㅎㅎ combi 함수가 이상한 것 같습니다. 예를 들어 3 3 0 0 0 0 0 0 0 0 2 이렇게 입력을 했을 때 모든 경우의수를 확인할 수 있을까요? 디버깅코드는 다음과 같습니다. #include 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>& 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 << " CLEAR "; 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> 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점은 제가 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.