5-X 문제 틀린로직

Question

안녕하세요 큰돌선생님.. 해당 문제를 풀었는데 예제 입력 1번과 2번까지는 잘 나오는데 나머지가 틀렸다고해서 질문드립니다. 선생님 코드와 아주 큰 틀에서는 비슷한것 같긴한데, 제 코드가 우선 깔끔하지는 못한것 같습니다. 따로 변환된 좌표를 받아서 원복시키는것이 아닌 flag 변수를 사용하여 원복시키는 코드로 작성하였습니다.. 오래 생각해보았는데 진전이 없어 질문드립니다. 혹시 어떤 부분이 잘못된 로직인가요?? http://boj.kr/468e705a31f141d7aaf8dea5cc6f4dfd

큰돌 · Answer

안녕하세요 명운님 ㅎㅎ 예제3번을 넣고 디버깅해보시면 1 10 10 10 10 10 10 1 10 10 10 10 10 0 1 10 10 10 10 0 0 1 10 10 10 0 0 0 1 10 10 0 0 0 0 1 10 이런식으로 뜨는데요. move자체가 이상한 것 같습니다. 디버깅 코드 #include using namespace std; const int dy[] = {-1, 0, 1, 0}; const int dx[] = {0, 1, 0, -1}; const int INF = (int)1e9; int N, M, ret = INF, a[10][10]; struct A { int y, x, id; }; vector v; int check() { int cnt = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (a[i][j] == 0) cnt++; } } return cnt; } void d(){ for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cout << a[i][j] << " "; } cout << ' '; } } void move(int y, int x, int dir, int flag) { int ny = y + dy[dir]; int nx = x + dx[dir]; if (ny < 0 || nx < 0 || ny >= N || nx >= M) return; if (a[ny][nx] == 6) return; a[ny][nx] = flag; move(ny, nx, dir, flag); } void go(int idx) { if (idx == v.size()) { int tmp = check(); if(tmp < ret){ ret = tmp; d(); } return; } int y = v[idx].y, x = v[idx].x, id = v[idx].id; if (id == 1) { for (int i = 0; i < 4; i++) { move(v[idx].y, v[idx].x, i, 10); go(idx + 1); move(v[idx].y, v[idx].x, i, 0); } } else if (id == 2) { move(y, x, 0, 10); move(y, x, 2, 10); go(idx + 1); move(y, x, 0, 0); move(y, x, 2, 0); move(y, x, 1, 10); move(y, x, 3, 10); go(idx + 1); move(y, x, 1, 0); move(y, x, 3, 0); } else if (id == 3) { move(y, x, 0, 10); move(y, x, 1, 10); go(idx + 1); move(y, x, 0, 0); move(y, x, 1, 0); move(y, x, 1, 10); move(y, x, 2, 10); go(idx + 1); move(y, x, 1, 0); move(y, x, 2, 0); move(y, x, 2, 10); move(y, x, 3, 10); go(idx + 1); move(y, x, 2, 0); move(y, x, 3, 0); move(y, x, 3, 10); move(y, x, 4, 10); go(idx + 1); move(y, x, 3, 0); move(y, x, 4, 0); } else if (id == 4) { move(y, x, 3, 10); move(y, x, 0, 10); move(y, x, 1, 10); go(idx + 1); move(y, x, 3, 0); move(y, x, 0, 0); move(y, x, 1, 0); move(y, x, 0, 10); move(y, x, 1, 10); move(y, x, 2, 10); go(idx + 1); move(y, x, 0, 0); move(y, x, 1, 0); move(y, x, 2, 0); move(y, x, 1, 10); move(y, x, 2, 10); move(y, x, 3, 10); go(idx + 1); move(y, x, 1, 0); move(y, x, 2, 0); move(y, x, 3, 0); move(y, x, 2, 10); move(y, x, 3, 10); move(y, x, 0, 10); go(idx + 1); move(y, x, 2, 0); move(y, x, 3, 0); move(y, x, 0, 0); } else { move(y, x, 0, 10); move(y, x, 1, 10); move(y, x, 2, 10); move(y, x, 3, 10); go(idx + 1); move(y, x, 0, 0); move(y, x, 1, 0); move(y, x, 2, 0); move(y, x, 3, 0); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 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] != 6 && a[i][j] != 0) v.push_back({i, j, a[i][j]}); } } go(0); cout << ret << ' '; return 0; } 이럴 때는 좀 더 간소화해서 디버깅하시는게 좋습니다. #include using namespace std; const int dy[] = {-1, 0, 1, 0}; const int dx[] = {0, 1, 0, -1}; const int INF = (int)1e9; int N, M, ret = INF, a[14][14]; struct A { int y, x, id; }; vector v; int check() { int cnt = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (a[i][j] == 0) cnt++; } } return cnt; } void d(){ for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cout << a[i][j] << " "; } cout << ' '; } } void move(int y, int x, int dir, int flag) { int ny = y + dy[dir]; int nx = x + dx[dir]; if (ny < 0 || nx < 0 || ny >= N || nx >= M) return; if (a[ny][nx] == 6) return; a[ny][nx] = flag; move(ny, nx, dir, flag); } void go(int idx) { if (idx == v.size()) { int tmp = check(); if(tmp < ret){ ret = tmp; cout << ret << ' '; d(); } return; } int y = v[idx].y, x = v[idx].x, id = v[idx].id; if (id == 1) { for (int i = 0; i < 4; i++) { move(y, x, i, 10); go(idx + 1); move(y, x, i, 0); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 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] != 6 && a[i][j] != 0) v.push_back({i, j, a[i][j]}); } } go(0); cout << ret << ' '; return 0; } 이렇게 하시구 보시면 되는데요. 여기서 이걸 그대로 예제 3 넣고 돌리시면 문제점이 명확히 보입니다. 12 1 0 10 10 10 10 0 1 10 10 10 10 0 10 1 10 10 10 0 10 0 1 10 10 0 10 0 0 1 10 0 10 0 0 0 1 바로 이부분. 가장 첫번째 CCTV의 경우 오른쪽이나 아래로 가야되는데 중간에 0이 있는 것을 볼 수 있죠? 명운님은 0을 10으로 만든다. 그리고 10을 0으로 만든다는 것을 기반으로 로직을 짜셨는데 이 경우 그 이전에 만들어진 10도 0으로 만들어져버리게 됩니다. 즉, 10 10 10 10 이렇게 감시 해놨다가 갑자기 어떤 idx 시점에서 이 10이 10 10 0 10 이런식으로 될 수도 있는 것이죠. a -> b -> c 이렇게 정점을 거치면서 상태값을 쌓아가야하는데 c부분에서 a의 상태값을 건드리게 되는 것입니다. 이부분 때문에 틀리는 것 같습니다. 고쳐보시겠어요? 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.