[1차] 프렌즈4블록(2018 카카오 블라인드 채용)

문제 링크

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

 

 

풀이

어려웠다... 실제였으면 이것만 풀었을거같다.

check() 함수를 통해서( m 1) m이 자기 자신일 때, 1, 2, 3이 자신의 문자(char)와 같은 지 비교하여 bool형을 return 하였다.                         ( 2  3)

그리고 제일 큰 while 문은 터뜨린 것이(지워진 블락이) 없을 때 탈출하도록 하였다.

check() 함수의 인덱스 초과를 방지하기 위해 2중 for문의 m-1, n-1로 돌렸으며 copy본에 '0' 문자로 바꿔주었다.

이유는, DFS로 풀기에는 중복을 처리해줘야되기 때문에 차라리 덮어씌우자는 마인드로 copy본을 만들고 나중에 swap해주었다. 그리고 밑에서부터 '0'이 있으면 위에꺼를 밑으로 내려주었다. 이를 반복하여 마지막에 '0' 개수(지워진 블락)를 세주는 것을 return 해주면 된다.

 

요약

1) 터뜨릴 수 있는지 확인하는 check()함수 구현

2) 2중 for문 돌아서 터뜨리고 3중 for문 돌려서 밑으로 땡겨주었다.(지워진 블락만 할까 했는데 조건 거는게 많을까봐...)

3) 마지막에 2중 for문 돌아서 '0' 개수 세줌(막상 코드를 리뷰하다보니 터뜨릴 때마다 개수 세줘도 될거같지만 조건을 걸어야 되므로 안했다)

 

 

#include <string>
#include <vector>

using namespace std;

bool check(int y, int x, vector<string> board)
{
    char c = board[y][x];
    if(c=='0') return false;
    bool equal = true;
    equal &= (c == board[y][x+1]);      // right
    equal &= (c == board[y+1][x]);      // down
    equal &= (c == board[y+1][x+1]);    // cross
    return equal;
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    while(true)
    {
        bool checked = false;
        vector<string> copy(board);
        for(int y=0; y<m-1; y++)            // segment fault 방지
        {
            for(int x=0; x<n-1; x++)        // segment fault 방지
            {
                if(check(y, x, board))
                {
                    copy[y][x] = '0';
                    copy[y][x+1] = '0';
                    copy[y+1][x] = '0';
                    copy[y+1][x+1] = '0';
                    checked = true;
                }
            }
        }
        swap(board, copy);
        if(!checked) break;     // 터뜨린 것이 없다.
        else
        {
            for(int y=m-1; y>=0; y--)
            {
                for(int x=0; x<n; x++)
                {
                    if(board[y][x] == '0')
                    {
                        for(int k=y; k>=0; k--)
                        {
                            if(board[k][x] != '0')
                            {
                                board[y][x] = board[k][x];
                                board[k][x] = '0';
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
    for(int y=0; y<m; y++)
    {
        for(int x=0; x<n; x++)
        {
            if(board[y][x] == '0') answer++;
        }
    }
    
    return answer;
}