[C++] 프로그래머스 [1차] 프렌즈

 

https://school.programmers.co.kr/learn/courses/30/lessons/17679

프로그래머스

 

목차

• 문제
• 풀이
• 코드

문제

입력

입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다. 

board는 길이 n인 문자열 m개의 배열로 주어진다. 

블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

제한사항

2 ≦ n, m ≦ 30

풀이

1. 시뮬레이션 문제의 황금률: "상태 변화의 분리 (Phase Separation)"

• 보드의 상태가 변하는 문제(퍼즐, 테트리스, 애니팡 류)를 풀 때는 '탐색'과 '상태 변경'을 동시에 하면 절대 안 된다. (기존에 하다가 실패했다. 단일책임원칙... 지키자. 일단 다 분리하고 나중에 합치자.)
  • 찾으면서 동시에 지우거나, 지우면서 동시에 내리면 기존 보드가 망가져서 다음 탐색에 악영향을 미친다.
• 해결책: 좌표 수집(Find) ➔ 한 번에 지우기(Erase) ➔ 한 번에 중력 적용(Gravity)처럼 각 단계를 완전히 독립적인 루프(또는 함수)로 쪼개야 한다.

2. 중력(Gravity) 알고리즘의 O(N) 최적화 테크닉

• 블록을 밑으로 떨어뜨리는 로직을 짤 때, 지워진 빈칸의 모양(행-2 등)에 의존하거나 버블 정렬처럼 한 칸씩 스왑(Swap)하며 내릴 필요가 없다는 점.
  • 기존에는 그냥 행-2부터 첫번째 행까지 while문 돌리면 되는 거 아니야? - A()B()C는 어떻게 해결할 건데.
  • 버블정렬로 빈칸을 가장 앞으로 하면 되는 거 아니야? - 시간복잡도 O(n^2)
• 해결책 (주워 담기 기법):
  1. 각 열(Column)마다 맨 아래부터 위로 훑으면서 살아남은 블록만 queue(또는 vector)에 순서대로 쏙쏙 주워 담는다.
  2. 해당 열을 전부 빈칸('0')으로 초기화한다.
  3. 다시 맨 아래부터 큐에 담아둔 블록을 차곡차곡 꺼내어 채워 넣는다.

3. 중복되는 영역의 카운트 처리 방법 (2x3, 3x3 등)

• 2x2 블록 여러 개가 겹쳐서 지워질 때 중복 카운트를 어떻게 방지할까.
• 해결책: 4칸이 묶여있다고 해서 4칸 전체를 한 번에 검사하려고 복잡하게 짜지 말 것.
  • 각 칸을 지울 때마다 "이 칸이 이미 지워진 빈칸('0')이 아닐 때만 정답(answer)을 1 증가시키고 빈칸으로 바꾼다"라고 아주 단순하게 개별 처리하면 중복 문제가 완벽히 해결된다.

4. 면접관이 좋아하는 클린 코드 (리팩토링 요 요소)

• 매직 넘버 제거: 코드에 의미 없는 숫자나 문자(예: '0')를 하드코딩하지 않고, const char EMPTY = '0';처럼 상수로 빼내어 가독성과 유지보수성을 높였다.
• 방향 배열 최적화: 2x2를 탐색할 때, 기준점 (0,0)까지 포함하여 dr[4], dc[4]로 묶어버리면 불필요한 예외 처리(if문) 없이 for문 하나로 4칸을 깔끔하게 처리할 수 있다.

코드

리팩토링 전 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

// 그냥 구현 같은데요. 그냥 해보겠습니다.
/*
1. board의 행과 열을 각각 n-1, r-1까지 순회하면서
[행][열], [행][열+1], [행+1][열], [행+1][열+1]이 모두 같다면('0'이 아니라면) vector 배열에 {행, 열}을 넣어.
2. 해당 배열에 원소가 있다면
해당 배열을 순회하면서 해당 board[행][열], [행][열+1], [행+1][열], [행+1][열+1]을 모두 '0' 표시로 바꿔. (지우기)
3. 밀기
같은 열에서 가장 밑행부터 확인하면서 '0'이 없다면 해당 값을 저장하고 마지막에 가장 밑 행부터 차례대로 밀어 넣어.
4. 1~3번을 해당 배열이 비었을 때까지 실행해. 
*/

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    
    int dr[3] = {0, 1, 1};
    int dc[3] = {1, 0, 1};
    
    while (true) {
        vector<pair<int, int>> arr;
        
        // 2*2 찾아서 해당 배열 저장
        for (int r = 0; r < m - 1; ++r) {
            for (int c = 0; c < n - 1; ++c) {
                if (board[r][c] == '0') continue;
                
                bool is_erase = true;
                for (int i = 0; i < 3; ++i) {
                    int nr = r + dr[i];
                    int nc = c + dc[i];
                    
                    if (board[r][c] != board[nr][nc] || board[nr][nc] == '0') {
                        is_erase = false;
                        break;
                    }
                }
                
                if (is_erase) {
                    arr.push_back({r, c});
                }
            }
        }
        
        if (arr.empty()) break;
        
        // 지우기
        for (auto& pos : arr) {
            int r = pos.first;
            int c = pos.second;
            
            if (board[r][c] != '0') {
                board[r][c] = '0';
                answer++;
            }
            
            for (int i = 0; i < 3; ++i) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                
                if (board[nr][nc] != '0') {
                    board[nr][nc] = '0';
                    answer++;
                }
            }
        }
        
        // 밀어 넣기
        for (int c = 0; c < n; ++c) {
            queue<char> q;
            
            // '0'이 아닌 값을 저장
            for (int r = m - 1; r >= 0; --r) {
                if (board[r][c] != '0') {
                    q.push(board[r][c]);
                }
                
                board[r][c] = '0';
            }
            
            // 해당 열 갱신
            for (int r = m - 1; r >= 0; --r) {
                if (q.empty()) break;
                
                board[r][c] = q.front();
                q.pop();
            }
        }
    }
    
    return answer;
}

 

리팩토링 후 코드 (함수로 나누고 매직넘버, 변수 정리)

#include <string>
#include <vector>
#include <queue>

using namespace std;

// 그냥 구현 같은데요. 그냥 해보겠습니다.
/*
1. board의 행과 열을 각각 n-1, r-1까지 순회하면서
[행][열], [행][열+1], [행+1][열], [행+1][열+1]이 모두 같다면('0'이 아니라면) vector 배열에 {행, 열}을 넣어.
2. 해당 배열에 원소가 있다면
해당 배열을 순회하면서 해당 board[행][열], [행][열+1], [행+1][열], [행+1][열+1]을 모두 '0' 표시로 바꿔. (지우기)
3. 밀기
같은 열에서 가장 밑행부터 확인하면서 '0'이 없다면 해당 값을 저장하고 마지막에 가장 밑 행부터 차례대로 밀어 넣어.
4. 1~3번을 해당 배열이 비었을 때까지 실행해. 
*/

const char EMPTY = '0';
using Position = pair<int, int>;

const int dr[4] = {0, 0, 1, 1};
const int dc[4] = {0, 1, 0, 1};

vector<Position> findMatchedBlocks(int m, int n, const vector<string>& board) {
    vector<Position> matched;
    for (int r = 0; r < m - 1; ++r) {
        for (int c = 0; c < n - 1; ++c) {
            char current = board[r][c];
            if (current == EMPTY) continue;
            
            bool is_match = true;
            for (int i = 1; i < 4; ++i) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (board[nr][nc] != current) {
                    is_match = false;
                    break;
                }
            }
            
            if (is_match) {
                matched.push_back({r, c});
            }
        }
    }
    
    return matched;
}

int eraseBlocks(const vector<Position>& matched, vector<string>& board) {
    int erased_count = 0;
    
    for (const auto& pos : matched) {
        int r = pos.first;
        int c = pos.second;
        
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if (board[nr][nc] != EMPTY) {
                board[nr][nc] = EMPTY;
                erased_count++;
            }
        }
    }
    
    return erased_count;
}

void applyGravity(int m, int n, vector<string>& board) {
    for (int c = 0; c < n; ++c) {
        queue<char> surviving_blocks;
        
        for (int r = m - 1; r >= 0; --r) {
            if (board[r][c] != EMPTY) {
                surviving_blocks.push(board[r][c]);
                board[r][c] = EMPTY;
            }
        }
        
        for (int r = m - 1; r >= 0 && !surviving_blocks.empty(); --r) {
            board[r][c] = surviving_blocks.front();
            surviving_blocks.pop();
        }
    }
}

int solution(int m, int n, vector<string> board) {
    int total_erased = 0;
    
    while (true) {
        vector<Position> matched = findMatchedBlocks(m, n, board);
        
        if (matched.empty()) {
            break;
        }
        
        total_erased += eraseBlocks(matched, board);
        
        applyGravity(m, n, board);
    }
    
    return total_erased;
}