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

이명운님의 프로필 이미지
이명운

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

5-X

5-X 문제 틀린로직

작성

·

212

0

안녕하세요 큰돌선생님..

해당 문제를 풀었는데 예제 입력 1번과 2번까지는 잘 나오는데 나머지가 틀렸다고해서 질문드립니다.

선생님 코드와 아주 큰 틀에서는 비슷한것 같긴한데, 제 코드가 우선 깔끔하지는 못한것 같습니다.

따로 변환된 좌표를 받아서 원복시키는것이 아닌 flag 변수를 사용하여 원복시키는 코드로 작성하였습니다..

오래 생각해보았는데 진전이 없어 질문드립니다. 혹시 어떤 부분이 잘못된 로직인가요??

http://boj.kr/468e705a31f141d7aaf8dea5cc6f4dfd

 

c++코딩-테스트

답변 1

1

큰돌님의 프로필 이미지
큰돌
지식공유자

안녕하세요 명운님 ㅎㅎ

예제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 <bits/stdc++.h>
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<A> 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 << '\n';
    }
}
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 << '\n';
    return 0; 
}

 

이럴 때는 좀 더 간소화해서 디버깅하시는게 좋습니다. 

#include <bits/stdc++.h>
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<A> 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 << '\n';
    }
}
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 << '\n';
            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 << '\n';
    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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

 

이명운님의 프로필 이미지
이명운
질문자

감사합니다! 알려주신 부분을 기반으로 수정해보겠습니다!

항상 감사합니다ㅎㅎ

이명운님의 프로필 이미지
이명운

작성한 질문수

전체 Q&A
질문하기