프로그래머스 프렌즈4블록 (C++)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록

문제 요약

 

1. 2*2블록이 모두 같은 그림으로 이루어져 있으면, 해당 블록은 사라지고 사라진 블록의 갯수만큼 점수를 얻습니다.

2. 블록은 서로 겹쳐서 터질 수 있습니다. 

3. 블록은 모두 한꺼번에 사라집니다.

4. 터진 블록으로 인해 빈 공간이 생길 경우, 해당 블록의 가장 가까운 윗줄의 다른 블록이 빈 공간으로 내려옵니다.

 

핵심 포인트

 

블록을 터트리고 생기는 빈 공간을 메꿀때의 알고리즘이 중요합니다.

반드시 터진 블록의 자리에만 다른 블록이 채워지는 것은 아닙니다.

터진 블록을 채우느라 다른 블록이 자리를 매꾸고, 그렇게 새로이 빈 공간이 탄생된 다른 블록 자리에도 또 다른 블록을 채워야 할 수 있습니다.

 

문제 풀이

 

1. 편의상 n과 m의 값을 전역변수로 저장합니다. 동시에 정답값과 터트린 블록의 점수인 temp 변수를 선언합니다.

while문은 temp의 값이 0이 될때까지, 즉, 더 이상 터트릴 블록이 없을때까지 계속됩니다.

int h,w,ny,nx,my[]={0,1,1},mx[]={1,0,1}; // 전역 변수

... 

int solution(int m, int n, vector<string> board) {
    h = m, w = n;
    int answer = 0, temp = 0;
    while(true){
        temp = friends(board);
        answer += temp;
        if(temp==0) break;
    }
    return answer;
}

 

2. 다음은 friends함수의 내부입니다. 단계별로 이해해봅시다.

int friends(vector<string> &board){
    int score = 0; // 1
    vector<vector<bool>> ch(h,vector<bool>(w,false));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(board[i][j]!=' '){
                int temp = 1;
                for(int a=0; a<3; a++){
                    ny = i+my[a];
                    nx = j+mx[a];
                    if(ny<0||ny>=h||nx<0||nx>=w) break;
                    if(board[ny][nx]==board[i][j]){
                        temp++;
                    }
                }
                if(temp==4){
                    if(ch[i][j]) temp--;
                    else ch[i][j] = true;
                    for(int a=0; a<3; a++){
                        ny = i+my[a];
                        nx = j+mx[a];
                        if(ny<0||ny>=h||nx<0||nx>=w) break;
                        if(ch[ny][nx]) temp--;
                        else ch[ny][nx] = true;
                    }
                    score+=temp;
                }
            }
        }
    }  // 터트린 블록들은 공란으로 표시함
    for(int i=0; i<h; i++){ // 2
        for(int j=0; j<w; j++){
            if(ch[i][j]) board[i][j] = ' ';
        }
    }
    // 터트릴 블록들은 true로 표시함
    for(int i=h-1; i>=0; i--){ // 3
        for(int j=0; j<w; j++){
            if(board[i][j]==' '){
                for(int a=i-1; a>=0; a--){
                    if(a<0) break;
                    if(board[a][j]!=' '){
                        board[i][j] = board[a][j];
                        board[a][j] = ' ';
                        break;
                    }
                }
            }
        }
    }
    return score;
}

 

3. friends 함수의 첫 번째 구역입니다.

    int score = 0; // 1
    vector<vector<bool>> ch(h,vector<bool>(w,false)); // 2
    for(int i=0; i<h; i++){ // 3
        for(int j=0; j<w; j++){
            if(board[i][j]!=' '){ // 4 
                int temp = 1; // 5
                for(int a=0; a<3; a++){ // 6
                    ny = i+my[a];
                    nx = j+mx[a];
                    if(ny<0||ny>=h||nx<0||nx>=w) break; // 7
                    if(board[ny][nx]==board[i][j]){ // 8
                        temp++;
                    }
                }
                if(temp==4){ // 9
                    if(ch[i][j]) temp--; // 10
                    else ch[i][j] = true; // 11 
                    for(int a=0; a<3; a++){ // 12
                        ny = i+my[a];
                        nx = j+mx[a];
                        if(ny<0||ny>=h||nx<0||nx>=w) break; // 13
                        if(ch[ny][nx]) temp--; // 14
                        else ch[ny][nx] = true; // 15
                    }
                    score+=temp; /// 16
                }
            }
        }
    } 

(1) score함수는 한 번에 터지는 블록의 갯수를 세어줍니다.

(2) bool문을 만들고 모든 값은 false로 초기화합니다.

(3) 블록판의 사이즈만큼 for문을 진행합니다.

(4) 만약 현재 칸이 공란이 아닐 경우...

->(5) 임시 score값인 temp를 1로 선언합니다.

->(6) 0부터 2까지 for문을 돌려줍니다. 이렇게 3가지 값만 for문으로 구하는 이유는, 2*2의 블록만 터트릴 수 있기 때문입니다. 참고로 my, mx배열은 전역변수로 이미 선언되어있습니다.

-> (7) 만약 새로운 값의 위치가 범위를 초과한다면, 바로 빠져나옵니다.

-> (8) 만약 새로운 값이 현재 값과 동일하다면 temp를 +1 합니다.

(9) 그렇게 구한 temp가 4일 경우 ...

-> (10) 만약 현재 위치가 이미 방문했던 곳이라면, temp를 -1해줍니다. 이미 터트린 블록을 중복해서 터트릴 수 없기 때문입니다.

참고로 이러한 경우는 다음의 그림과 같습니다. 

-> (11) 방문한 적이 없다면 방문 표시를 해줍니다.

-> (12) 현재 위치를 기준으로 2*2의 블록만큼 for문을 돌려줍니다.

-> (13) 만약 새로운 값의 위치가 범위를 초과한다면 바로 빠져나옵니다.

-> (14) 만약 새로운 값의 위치가 이미 방문한 곳이라면, temp를 -1해줍니다.

-> (15) 그렇지 않을 경우 방문표시릉 해줍니다.

(16) 그렇게 구한 temp를 score에 더해줍니다.

 

4. 터트린 블록들을 모두 공란으로 표시합니다.

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(ch[i][j]) board[i][j] = ' ';
        }
    }

 

5. 다음은 빈 공간으로 새로운 블록이 내려오는 알고리즘입니다.

    for(int i=h-1; i>=0; i--){ // 1
        for(int j=0; j<w; j++){
            if(board[i][j]==' '){ // 2
                for(int a=i-1; a>=0; a--){ // 3
                    if(a<0) break; // 4
                    if(board[a][j]!=' '){ // 5
                        board[i][j] = board[a][j]; // 6
                        board[a][j] = ' '; // 7
                        break; // 8
                    }
                }
            }
        }
    }
    return score; // 9

(1) 맨 아래줄부터 for문을 진행합니다. 세로는 맨 아래줄이여야 하지만, 가로는 상관없으니 0부터 시작합니다.

(2) 만약 현재 블록이 공란이라면...

-> (3) 현재 위치의 바로 윗줄부터 0번째 줄까지 for문을 진행합니다.

-> (4) 만약 새로운 세로 위치가 음수라면, 해당 for문을 빠져나옵니다.

-> (5) 만약 새로운 위치가 공란이 아닐 경우엔...

     -> (6) 현재 위치에 새로운 위치의 블록을 넣어줍니다.

     -> (7) 새로운 위치는 공란으로 표시합니다.

     -> (8) 해당 for문을 종료합니다.

(9) 이렇게 구한 score를 반환합니다.

 

6. 이렇게 블록을 터트린 다음, 더 이상 터트릴 블록이 없을 경우 while문을 빠져나와 정답을 반환합니다.

 

#include <string>
#include <vector>

using namespace std;

int h,w,ny,nx,my[]={0,1,1},mx[]={1,0,1};

int friends(vector<string> &board){
    int score = 0;
    vector<vector<bool>> ch(h,vector<bool>(w,false));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(board[i][j]!=' '){
                int temp = 1;
                for(int a=0; a<3; a++){
                    ny = i+my[a];
                    nx = j+mx[a];
                    if(ny<0||ny>=h||nx<0||nx>=w) break;
                    if(board[ny][nx]==board[i][j]){
                        temp++;
                    }
                }
                if(temp==4){
                    if(ch[i][j]) temp--;
                    else ch[i][j] = true;
                    for(int a=0; a<3; a++){
                        ny = i+my[a];
                        nx = j+mx[a];
                        if(ny<0||ny>=h||nx<0||nx>=w) break;
                        if(ch[ny][nx]) temp--;
                        else ch[ny][nx] = true;
                    }
                    score+=temp;
                }
            }
        }
    }  // 터트린 블록들은 공란으로 표시함
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(ch[i][j]) board[i][j] = ' ';
        }
    }
    // 터트릴 블록들은 true로 표시함
    for(int i=h-1; i>=0; i--){
        for(int j=0; j<w; j++){
            if(board[i][j]==' '){
                for(int a=i-1; a>=0; a--){
                    if(a<0) break;
                    if(board[a][j]!=' '){
                        board[i][j] = board[a][j];
                        board[a][j] = ' ';
                        break;
                    }
                }
            }
        }
    }
    return score;
}

int solution(int m, int n, vector<string> board) {
    h = m, w = n;
    int answer = 0, temp = 0;
    while(true){
        temp = friends(board);
        answer += temp;
        if(temp==0) break;
    }
    return answer;
}