[Programmers] 17679 프렌즈4블록 (C++)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17679?language=cpp

프로그래머스

애니팡이 생각나는 문제.

 

 

풀이

구현 문제

어떻게 쉽게 구현할 것인가…에 대한 식견

1) 처음 생각한 풀이

1. board를 순회하며 2x2에 모두 같은 값이 있는지 판단
2. 같은 값이 존재하는 경우 board에 표시
   • 대문제→소문자로 변경
   • 바꿀 때마다 cnt로 체크하기
   • cnt가 0이면 바꿀 값이 없다는 의미므로 종료!
   • [문제] 이후 순회할 때 겹치는 문자 예외 존재!
3. 삭제
   • 삭제시 소문자들 모두 X로 바꾸기
4. 아래에서부터 순회하며 삭제한 칸인 경우 위에서 밀기
5. 바꿀 값이 없을 때까지 반복

2) 개선점

• board에 직접 기록하면 너무 복잡하고 예외가 많다.
• → set을 이용하면 그냥 넣어도 중복허락없이 자동으로 관리 가능!
• 훨씬 더 깔끔하게 처리할 방법을 적용
• 메모리를 더 사용하더라도 그냥 구현하자

3) 수정한 풀이

1. board를 순회하며 삭제할 2x2블록이 존재하는지 확인
   • flag변수로 확인하여 반복 여부 체크
   • set을 사용하여 같은 경우, 좌표값 모두 넣기
   • 이때 이미 삭제한 X는 예외로 넘겨야 함!
2. set을 순회하며 삭제
   • 삭제 후 set.clear()
3. 아래에서부터 순회하며 X인 칸은 위에서 땡기기

4) 배운점

• 중복을 허락하지 않는 값들은 set을 이용하여 편하게 관리 가능
• set에 대한 기본 문법들!

 

코드

#include <string>
#include <iostream>
#include <vector>
#include <set>

using namespace std;

char mp[30][30];
int M, N;
int dy[3] = { 1, 0, 1 }; // 크기 3으로 수정
int dx[3] = { 0, 1, 1 }; // 크기 3으로 수정

set<pair<int, int>> s;

bool check(int cy, int cx) {
    char cmp = mp[cy][cx];
    for (int i = 0; i < 3; i++) {
        int ny = cy + dy[i];
        int nx = cx + dx[i];
        if (mp[ny][nx] != cmp) return false;
    }
    return true;
}


int solve() {
    int ans = 0;

    while (true) {
        bool flag = false;

        // 지울 좌표 set에 추가
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (mp[i][j] == 'X') continue;
                int cy = i;
                int cx = j;
                
                if (i <= M - 2 && j <= N - 2 && check(cy, cx)) {
                    flag = true;
                    s.insert({ cy, cx });
                    s.insert({ cy + 1, cx });
                    s.insert({ cy, cx + 1 });
                    s.insert({ cy + 1, cx + 1 });
                }
            }
        }

        if (!flag) break;

        //지우기
        
        for (auto cor : s) {
            mp[cor.first][cor.second] = 'X';
            ans++;
        }
        s.clear();
        // 아래로 밀기        
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 0; j < M; j++) {
                if (mp[i][j] == 'X') {
                    int k = i;

                    // 상단의 값 찾기
                    while (k >= 0 && mp[k][j] == 'X') {
                        k--;
                    }

                    // 값 바꾸기
                    if (k >= 0) {
                        mp[i][j] = mp[k][j];
                        mp[k][j] = 'X';
                    }

                }
            }
        }


    }
    return ans;

}



int solution(int m, int n, vector<string> board) {
    M = board.size();
    N = board[0].size();

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            mp[i][j] = board[i][j];
        }
    }
    int answer = solve();
    return answer;
}

// 디버깅용 main 함수
int main(void) {

    M = 6;
    N = 6;
    vector<string> brd;
    brd = vector<string>(N);
    for (int i=0; i < N; i++) {
        cin >> brd[i];
    }

    cout << solution(M, N, brd);

}