14502 다시금 질문드립니다..!

Question

http://boj.kr/840f45d321eb47839eab789e324f7551 세번째 질문.. 다시 드립니다 ㅠㅠ combi함수에서.. 64~67라인에서 마지막에 pop_back()을 하는 이유도 이해 했습니다. 조합에서 각 재귀가 들어갈 때마다 넣고 재귀함수에서 나오면 빼서 다음 포문에서 골라서 다시 넣어야 하니까요. 다만 제가 묻고 싶은 점은.. 제 문제가 로직상 틀린 점이 없다고 생각했는데 정답 처리가 안나서 어디서 오류가 나는 지를 모르겠습니다 ㅠㅠ 제가 생각한 사고 방식은 다음과 같습니다. --- 74~79 라인에서 단순히 h벡터에 0인 좌표들을 넣어놓구요..(h는 조합이 될 후보군들의 좌표를 넣어놓은 벡터) ---- combi함수로 들어가.. 64~68라인에서 h벡터 에서 조합을 해서 s벡터에 좌표들을 넣습니다.(s는 세개를 조합하고 난 선정된 좌표들을 넣어놓은 벡터) ----- 31 라인에서 만약 3개의 좌표가 s벡터에 들어가면 32~36까지 visited 배열을 문제에서 준 초기 배열(== arr배열)로 초기화를 하구요. 38~40은 s벡터에 조합해둔 좌표들에 벽을 세웁니다(1로 바꿔줍니다.) 42~46에서 값이 2인 곳 즉 이미 바이러스가 있는 곳에서 dfs를 합니다. ---- 17~27까지 dfs를 하는데.. 이제 해당 좌표로 들어오면 바이러스가 전염된 걸로 보고(2로 바꿔줍니다.) 4방향 중 0인 곳에만 다시 방문을 해서 dfs를 합니다. ---- 48~58까지는 단순히 visited 배열 상의 안전지대 즉 값이 0인 곳을 카운팅 해서 기존의 ans와 값을 비교하여 더 큰 값을 측정합니다. 어느 라인에서 제가 실수를 해서 오답 판정을 받았을까요?

큰돌 · Answer

오... ㅎㅎ 이제 모든 코드를 이해하시고 맞왜틀까지 오셨군요. ㅎㅎ 축하드립니다. 완섭님. 제가 주석을 달아봤습니다. 해당부분 참고해주세요. 감사합니다. #define _CRT_SECURE_NO_WARNINGS #include using namespace std; int dy[4] = { 1,0,-1,0 }; int dx[4] = { 0,-1,0,1 }; int n, m; int arr[10][10]; int visited[10][10]; vector> h; vector> s; int ans = 0; void dfs(int y,int x) { visited[y][x] = 2; 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) continue; // 왜 벽일 때의 로직이 없죠? 벽은 통과 못합니다. 바이러스. if (visited[ny][nx] == 0) { dfs(ny, nx); } } } void combi(int k) { if (s.size() == 3) { // visited라는 임시 배열에다가 arr 설정 good for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { visited[i][j] = arr[i][j]; } } // 벽 세우기 : good for (int i = 0; i < 3; i++) { visited[s[i].first][s[i].second] = 1; } // 바이러스면 퍼진다 : good for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if(visited[i][j] == 2) dfs(i,j); } } int temp = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (visited[i][j] == 0) temp++; } } ans = max(temp, ans); return; } for (int i = k; i < h.size(); i++) { s.push_back(h[i]); combi(k + 1); s.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) h.push_back({ i,j }); } } combi(0); cout << ans; }