프로그래머스 lv2 - 프렌즈4블록 (자바) [2018 KAKAO BLIND RECRUITMENT]

문제

---

프로그래머스 lv2 - 프렌즈4블록

풀이

---

• 2 * 2형태의 정사각형 형태로 같은 블록인지 체크하면 되므로 매 위치마다 현 위치의 오른쪽, 대각선 아래, 아래를 체크
• 만약 4칸이 다 같으면 해당 칸들을 지워야 할 블록 list에 추가
• visited로 방문 처리를 하면 안되기 때문에 이미 지울 칸으로 선택되어 list에 들어간 칸이 또 list에 들어갈 수 있음
  -> 그러므로 이번 턴에 지워지는 블록 개수를 체크할 때 이미 지워진 칸이라면 개수를 카운팅 해주지 않도록 주의

어려웠던 점

---

문제를 꼼꼼히 읽지 않아서 그림만 대충 보고 아~ 이거 dfs로 같은 그림은 전부 탐색해서 사라지게 하면 되겠다 생각하고 로직을 bfs를 사용해서 구현했다. 그래서 테스트 케이스가 틀린 후 다시 문제를 확인하니 2*2 형태로 4개가 붙어있을 때만 지우는 것이었다.
문제를 꼼꼼히 읽자!

코드

---

import java.util.*;
class Solution {
    int m, n, ans;
    char[][] a;
    int[] dy = {0, 1, 1}; // 우측, 대각선 아래, 아래
    int[] dx = {1, 1, 0};
    public int solution(int m, int n, String[] board) {
        this.m = m; // 세로
        this.n = n; // 가로
        a = new char[m][n];
        for (int i = 0; i < board.length; i++)
            a[i] = board[i].toCharArray();

        while (true) {
            ArrayList<int[]> list = new ArrayList<>(); // 이번 턴에 깨진 블록 위치
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (a[i][j] == 'x') continue;
                    ArrayList<int[]> l = new ArrayList<>();
                    l.add(new int[]{i, j});
                    for (int dir = 0; dir < 3; dir++) {
                        int ny = i + dy[dir];
                        int nx = j + dx[dir];
                        if (ny < 0 || ny >= m || nx < 0 || nx >= n || a[ny][nx] == 'x' || a[i][j] != a[ny][nx]) break;
                        l.add(new int[]{ny, nx});
                    }
                    if (l.size() == 4) {
                        for (int[] p : l)
                            list.add(new int[]{p[0], p[1]});
                    }
                }
            }

            // 깨지는 블록 x로 처리
            for (int[] p : list) {
                if (a[p[0]][p[1]] != 'x') { // 중복되서 x처리하는 칸이 아닌 경우
                    a[p[0]][p[1]] = 'x';
                    ans++;
                }
            }

            // 열마다 남은 블록 한쪽으로 밀기
            for (int i = 0; i < n; i++) {
                int row = m - 1;
                for (int j = m - 1; j >= 0; j--) {
                    if (a[j][i] == 'x') continue;
                    a[row--][i] = a[j][i];
                }
                for (int j = row; j >= 0; j--)
                    a[j][i] = 'x';
            }

            if (list.size() == 0)
                break;
        }

        return ans;
    }
}