[ 백준 17822 ] 원판 돌리기 (C++)

[문제보기]

 

[해결과정]

 구조체에 deque를 생성하여 원판 1개에 대해 deque를 적용했다. (이 방법은 처음 시도 해봤다. 다음엔 구조체 안에 큐와 스택, 배열등을 넣어 고차원 배열을 생성하는데 주로 사용해봐야겠다.)

1. 원판 입력 받기

 - 구조체[원판번호].dq.push_back(번호) 를 활용하여 원판에 대한 정보를 입력받음

 

2. 원판 돌리기

 - 원판 돌리기 할 때 주의 할 점은, 입력 받은 x값의 배수에 해당하는 원판은 모두 돌려줘야한다. 그래서 반복문을 만들어 주고, x값의 배수가 n값 보다 커지면 빠져나오는 식으로 작성했다.

 - 원판 돌리기 turn 함수를 만들어 돌렸다.

 - turn 함수의 경우 deque로 원판을 만들었기에, 시계방향 및 시계반대방향으로 돌리는 것은 크게 어렵지 않았다. 시계방향으로 돌릴 경우 deque의 back()을 front()로 삽입 해주면 되고, 반대방향일 경우 front()를 back()으로 삽입하면 된다.

 

2. 인접한 수 지우기 (★★★★★) 

 - 이 문제의 핵심 기능인 것 같다. 본인은 좌우 확인, 상하 확인으로 2가지 경우를 나눠 생각했다. 절대값(abs)를 활용하여 같은 수가 붙어 있을 경우 양수일 경우 * -1 을 하여 음수로 고쳐줬다.

 

 - 좌우 확인의 경우, 원판 하나의 좌우를 뜻한다. 그래서 구조체 pan[i].dq 에 관해서만 생각하면 된다. 여기서 주의 할점은 원판 즉 원이기 때문에 처음과 끝은 붙어 있다는 것을 생각해야 한다. deque를 사용했기에 front()와 back()이 같은지 확인해줬다.

 

 - 상하 확인의 경우 원판과 원판에서 같은 위치의 deque에 속한 것을 비교해주면 된다. 코드로 예를들면 pan[i].dq[j] == pan[i+1].dq[j] 를 확인하는 것과 같다.

 

 - 위에서 만약 같은 수가 있어 지워진 경우가 1개라도 있다면 flag 변수를 설정한다. flag 변수가 1이라면 위에서 음수로 바꾼 수를 0으로 바꾼다. 0은 숫자가 삭제된 것과 의미가 같다. (문제에서 수는 1이상으로 제시되어 있다.)

 

 - 만약 flag 변수가 0이라면 숫자가 중복된 경우가 1개도 없으니, 모든 판의 deque를 돌며 0이 아닌 수 의 갯수를 구하고, 0이 아닌 수의 총합을 구한다. 갯수와 총합은 double 형을 선언해야 한다. (int 형의 경우 소수점 처리가 안된다.)

 

 - 총합/갯수를 double 형 변수에 넣고, 다시 모든 판의 deque를 돌며, 값이 평균보다 크면 +1, 작으면 -1을 한다. 물론 지워진 숫자 0을 만나면 continue 한다.

 

[소스코드]

#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;
 
const int MAX = 52;
 
struct Pan {
    deque <int> dq;
};
 
Pan pan[MAX];
int n, m, t;
 
// 1. 원판 돌리기
void turn(int x, int d, int k) {
    //k만큼 회전
    for (int i = 0; i < k; i++) {
        if (d == 0) {
            //시계방향으로 회전
            int temp = pan[x].dq.back();
            pan[x].dq.pop_back();
            pan[x].dq.push_front(temp);
        }
        else {
            //반시계방향으로 회전
            int temp = pan[x].dq.front();
            pan[x].dq.pop_front();
            pan[x].dq.push_back(temp);
        }
    }
    
}
 
// 2. 인접한 수 지우기
void deleteNum() {
    // 한번이라도 지워졌는지, 안지워졌는지 체크하는 flag
    // 지워지면 1, 한번도 안지워졌다면 0;
    int flag = 0;
 
    // 좌, 우, 위, 아래 확인
    // 좌, 우 확인
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
 
            if (j == m - 1) {
                //끝, 처음 비교
                if (pan[i].dq.front() == 0 || pan[i].dq.back() == 0) continue;
                if (abs(pan[i].dq.front()) == abs(pan[i].dq.back())) {
                    if (pan[i].dq[0] > 0) pan[i].dq[0] *= -1;
                    if (pan[i].dq[j] > 0) pan[i].dq[j] *= -1;
                    //pan[i].dq[0] *= -1;
                    //pan[i].dq[j] *= -1;
                    flag = 1;
                }
            }
            else {
                //좌, 우 비교
                if (pan[i].dq[j] == 0 || pan[i].dq[j+1] == 0) continue;
                if (abs(pan[i].dq[j]) == abs(pan[i].dq[j + 1])) {
                    if (pan[i].dq[j] > 0) pan[i].dq[j] *= -1;
                    if (pan[i].dq[j+1] > 0) pan[i].dq[j+1] *= -1;
                    //pan[i].dq[j] *= -1;
                    //pan[i].dq[j + 1] *= -1;
                    flag = 1;
                }
            }
 
        }
    }
    // 위, 아래 확인
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
 
            if ( pan[i].dq[j] == 0 || pan[i+1].dq[j] == 0) continue;
            if ( abs(pan[i].dq[j]) == abs(pan[i + 1].dq[j]) ) {
                if (pan[i].dq[j] > 0) pan[i].dq[j] *= -1;
                if (pan[i+1].dq[j] > 0)pan[i+1].dq[j] *= -1;
                //pan[i].dq[j] *= -1;
                //pan[i + 1].dq[j] *= -1;
                flag = 1;
            }
 
        }
    }
 
    
 
    // 하나도 바뀌지 않은게 있다면 평균 값 처리.
    if (flag == 1) {
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                if (pan[i].dq[j] < 0) pan[i].dq[j] = 0;
            }
        }
 
        //디버깅
        /*
        cout << "디버깅1" << endl;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                cout << pan[i].dq[j] << " ";
            }
            cout << endl;
        }
        cout << endl;
        */
        return;
    }
    else {
        //원판에 지워지지 않은 숫자의 갯수
        double cnt = 0;
        //원판에 지워지지 않은 숫자의 총합
        double sum = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                if (pan[i].dq[j] == 0) continue;
                cnt++;
                sum += pan[i].dq[j];
            }
        }
        //평균 값
        double avg = sum / cnt;
        //cout << "avg : " << avg << endl;
        
        //평균 값 보다 크면 -1, 작으면 +1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                if (pan[i].dq[j] > avg && pan[i].dq[j]>0) pan[i].dq[j] -= 1;
                else if (pan[i].dq[j] < avg && pan[i].dq[j]>0) pan[i].dq[j] += 1;
            }
        }
    }
 
    //디버깅
    /*
    cout << "디버깅2" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            cout << pan[i].dq[j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    */
}
 
int main() {
 
    cin >> n >> m >> t;
    
    //원판 입력
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            int temp;
            cin >> temp;
            pan[i].dq.push_back(temp);
        }
    }
 
    //원판 돌리기
    for (int i = 0; i < t; i++) {
        int x, d, k;
        cin >> x >> d >> k;
        
        // x의 배수 만큼 돌리기
        int temp = x;
        while (true) {
            if (temp > n) break;
            turn(temp, d, k);
            temp = temp + x;
        }
 
        // 인접한 수 지우기
        deleteNum();
    }
 
 
 
 
    //정답 출력
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            if (pan[i].dq[j] > 0) sum += pan[i].dq[j];
        }
    }
    cout << sum << endl;
 
    return 0;
}

 

 

[해결 과정 중 실수한 부분]

 1. 숫자를 지우는 과정에 있어 1 1 1 0 2 2 0 일 경우, 1이 연속으로 3개 붙어 있어 3개 모두 지워줘야한다. 나는 같은 숫자가 있을 경우 * -1을 하여 음수화 했는데, 예외처리를 하지않아 이미 음수인 것에 다시 * -1을 하여 양수가 되었다. 이를 해결하는 방법으로 이미 음수인 것은 continue하는 예외처리를 했다. (상하 확인도 마찬가지였다.)

 

 2. 평균 값을 구하는데 int 변수를 사용하여 값이 이상하게 출력 됐다. 문제가 착하게 출제 되었을 거란 착각 때문이였다. 이런 부분을 특히 주의해야 할 것 같다. 처음에 문제 풀 때 의문점은 들었었다. "크면 -1이고 작으면 +1 해주라는데, 그러면 같은 값은...?" 그래서 '>=' 사용했는데 우연히도 예제 답이 맞았었다... 그래서 더 힘들었다 ㅠㅠ... 평균값을 저장하는 변수를 double형으로 했는데도 답이 안나왔다. 문제는 갯수와 총합을 int로 해서 였다. 이 변수 또한 double형으로 해줘야 했다... 

 

 3. 디버깅(중간중간 출력하는 부분)의 위치를 잘못잡아 고생했다. 디버깅 위치도 지우지 않고 소스코드에 첨삭했다.

 

[관련 문제 혹은 비슷한 문제]

이  문제는 2019년 삼성 하반기 오후 역량테스트 1번이였다.관련 문제로 2번 17825 주사위 윷놀이가 있다.

17825번: 주사위 윷놀이