[1차] 프렌즈4블록

2x2일 경우 프렌즈 블록이 지워지고, 아래로 떨어진다.

터진 블록의 갯수

 

조건 

2 ≦ n, m ≦ 30

2x2일 경우 터진다. 중복 계산 가능

A~Z(대문자)로 입력이 주어짐

 

2x2 블록을 찾기위해 탐색을 해주고, 터질 위치를 새로운 배열을 만들어 체크해준다.

그후 블록을 제거해준다.(미리 제거하면 중복 계산 가능 조건에 어긋남)

반복 0 ~ m-1 // m++

  반복 n-1 ~ 0 // n--

열기준으로 (n-1,0)부터 (0,m-1) 탐색을 해준다. 공백이 있는 경우 index를 기준으로 위로 다시 반복 탐색

 

class Point {
        public int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    int[][] visit;
    int[] dx = new int[3];
    int[] dy;

    public Solution7() {
        dx = new int[] { 0, 1, 1 };
        dy = new int[] { 1, 1, 0 };
    }

    public boolean check(int n, int m, String[][] map) {
        boolean isHit = false;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                visit[i][j] = 0;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                String now = map[i][j];
                if(now.equals(" ")){
                    continue;
                }
                ArrayList<Point> dm = new ArrayList<Point>();

                for (int k = 0; k < 3; k++) {
                    int dxx = i + dx[k];
                    int dyy = j + dy[k];
                    
                    if (dxx < 0 || dxx >= n || dyy < 0 || dyy >= m || !now.equals(map[dxx][dyy])) {
                        dm.clear();
                        break;
                    }
                    if (now.equals(map[dxx][dyy])) {
                        dm.add(new Point(dxx, dyy));
                    }
                }
                if (!dm.isEmpty()) {
                    isHit = true;
                    visit[i][j] = 1;
                    for (int w = 0; w < dm.size(); w++) {
                        Point temp = dm.get(w);
                        visit[temp.x][temp.y] = 1;
                    }

                    // for (int q = 0; q < n; q++) {
                    //     for (int z = 0; z < m; z++) {
                    //         System.out.print(visit[q][z] + " ");
                    //     }
                    //     System.out.println();
                    // }
                    // System.out.println("===================================================");
                }

            }
        }
        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < m; j++) {
        //         System.out.print(visit[i][j] + " ");
        //     }
        //     System.out.println();
        // }
        // System.out.println("===================================================");
        return isHit;
    }

    public int solution(int n, int m, String[] board) {
        int answer = 0;
        visit = new int[n][m];
        String[][] map = new String[n][m];

        for (int i = 0; i < n; i++) {
            String[] temp = board[i].split("");
            for (int j = 0; j < m; j++) {
                map[i][j] = temp[j];
            }
        }

        while (true) {
            boolean hit = check(n, m, map);
            if (!hit) {
                break;
            } else {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        if (visit[i][j] == 1) {
                            map[i][j] = " ";
                            answer++;
                        }
                    }
                }
                //print(n, m, map);
                // fall_down
                for (int i = 0; i < m; i++) {
                    for (int j = n - 1; j >= 0; j--) {
                        boolean isSpace = false;
                        if (map[j][i].equals(" ")) {
                            //System.out.println("n : " + j +" m : " +i);
                            for (int k = j - 1; k >= 0; k--) {
                                if (!map[k][i].equals(" ")) {
                                    map[j][i] = map[k][i];
                                    map[k][i] = " ";
                                    isSpace = false;
                                    break;
                                }else{
                                    isSpace =true;
                                }

                            }
                        }
                        if(isSpace){
                            break;
                        }
                    }

                }
                //print(n, m, map);
            }

        }

        //System.out.println(answer);
        return answer;
    }

    public void print(int n, int m, String[][] map){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("============================");
    }

반복 배열에서 m을 n으로 잘못 적어서 한참 해맸다. 오타 조심

도중에 n x m이 헷갈렸다. 안 헷갈리게 계속 생각해야겠다.

백준의 뿌요뿌요와 유사한 문제였다.

 

코딩테스트 연습 2018 KAKAO BLIND RECRUITMENT [1차] 프렌즈4블록

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