[프로그래머스] 17679. 프렌즈4블록

문제 링크

[프로그래머스] 17679. 프렌즈4블록

풀이 과정

서로 인접한 2x2 형태의 블록이 지워지며, 지워진 공백을 위에서부터 채우는 시뮬레이션 문제입니다. 문제는 아래와 같이 크게 두 개의 부분으로 나누어 생각해 볼 필요가 있습니다.

1. 블록들을 지우는 작업
2. 지워진 블록들로 인해 생긴 공백을 위에서부터 차례로 메꾸는 작업

블록들을 지우는 작업은 다음과 같이 동작합니다. 한 지점을 기준으로 →, ↓, ↘︎ 방향의 블록들을 확인하고, 같으면 원본 배열에 표시를 합니다.

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        char c = copymap[i][j];

        if (j + 1 < n && i + 1 < m) {
            if (c != ' ' && copymap[i][j + 1] == c && copymap[i + 1][j] == c && copymap[i + 1][j + 1] == c) {
                exitflag = false;
                map[i][j] = map[i][j + 1] = map[i + 1][j] = map[i + 1][j + 1] = ' ';
            }
        }
    }
}

공백을 메꾸는 작업은 다음과 같이 동작합니다.

1. 아래에서부터 공백을 찾아 해당 위치(i)를 기준으로 가장 위로 가까운 블럭(target)을 찾습니다.
2. target 위치의 블록을 i 로 옮깁니다.

for (int j = 0; j < n; j++) {
    for (int i = m - 1; i >= 0; i--) {
        if (map[i][j] != ' ') continue;

        int target = i;
        while (target >= 0 && map[target][j] == ' ') target--;

        if (target == -1) continue;

        map[i][j] = map[target][j];
        map[target][j] = ' ';
    }
}

위 두 작업을 같은 2x2 블록을 더이상 찾을 수 없을 때까지 반복합니다.

코드

public class Main {
    public static int solution(int m, int n, String[] board) {
        int answer = 0;

        char[][] map = new char[m][n];
        char[][] copymap = new char[m][n];

        for (int i = 0; i < m; i++)
            map[i] = board[i].toCharArray().clone();

        while (true) {
            for (int i = 0; i < m; i++)
                copymap[i] = map[i].clone();

            boolean exitflag = true;

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    char c = copymap[i][j];

                    if (j + 1 < n && i + 1 < m) {
                        if (c != ' ' && copymap[i][j + 1] == c && copymap[i + 1][j] == c && copymap[i + 1][j + 1] == c) {
                            exitflag = false;
                            map[i][j] = map[i][j + 1] = map[i + 1][j] = map[i + 1][j + 1] = ' ';
                        }
                    }
                }
            }

            if (exitflag) break;

            for (int j = 0; j < n; j++) {
                for (int i = m - 1; i >= 0; i--) {
                    if (map[i][j] != ' ') continue;

                    int target = i;
                    while (target >= 0 && map[target][j] == ' ') target--;

                    if (target == -1) continue;

                    map[i][j] = map[target][j];
                    map[target][j] = ' ';
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == ' ') answer++;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
//        int m = 6;
//        int n = 6;
//        String[] board = {"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"};

        int m = 4;
        int n = 5;
        String[] board = {"CCBDE", "AAADE", "AAABF", "CCBBF"};

        solution(m, n, board);

    }
}