문제

[1차] 프렌즈4블록

풀이

이 문제에서는 블록이 2 * 2의 쌍으로 합쳐져야만 제거 가능하다는 것을 알아야 한다. 4개 이상 뭉쳐진 모든 경우의 수의 제거가 아니라는 점을 빨리 캐치 해야 한다 (문제를 제발 잘 읽기를...)

1. 글자 수 만큼 배열로 지정해서 2차원 배열로 넣어주어야 한다

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

• 이때 중첩 for 문을 만들기 싫기 때문에 toCharArray() 함수를 사용하여 한번에 넣어 준다

2. 2 * 2 범위의 같은 블록이 없을 때 까지 반복하기 위해 while 문을 사용하였다

		while (true) {
            int cnt = checkBlock(m, n);
            if (cnt > 0) {
                answer += cnt;
            } else {
                break;
            }
        }

3. 블록이 2 * 2 로 같은 경우 인지 확인 한다

	/**
     * 4개 씩 모여 있는 블록인지 체크
     * @param m 폭
     * @param n 높이
     * @return
     */
    static int checkBlock() {
        boolean[][] chk = new boolean[M][N];

        for (int i = 0; i < M - 1; i++) {
            for (int j = 0; j < N - 1; j++) {
                char c = map[i][j];
                // c가 블록이 내려 가서 없는 경우에는 다음 문자로 넘어간다
                if (c == '0') {
                    continue;
                }
                // 2 * 2 의 범위가 현재의 index 문자와 같은 경우 체크
                if (c == map[i + 1][j + 1] 
                		&& c == map[i][j + 1] 
                		&& c == map[i + 1][j]) {
                    chk[i][j] = true;
                    chk[i + 1][j + 1] = true;
                    chk[i][j + 1] = true;
                    chk[i + 1][j] = true;
                }
            }
        }
        return fallblock(chk);
    }

• 소스 상에서는 m - 1과 n - 1의 범위 에서만 체크 해주고 있다. 왜냐하면 아래서 chk[][] 에서 true 값으로 방문 한 값으로 바꿔줄 것인데 (0,0), (1,1) (0,1) (1,0) 의 범위 에서 check를 하도록 할 것이기 때문이다.
• c == '0' 의 경우에는 방문 해줄 필요가 없다. 떨어져서 아무것도 존재 하지 않는 칸이다

4. 열 단위로 블록을 재 갱신 해준다.

	/**
     * 블록 떨어뜨리고 떨어뜨린 블록 맞추기
     * @param n 높이
     * @param m 폭
     * @param chk
     * @return
     */
    static int fallblock(boolean[][] chk) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            List<Character> temp = new ArrayList<>(); // 새로 갱신될 열
            for (int j = M - 1; j >= 0; j--) { // 가장 마지막 행부터 탐색한다
                if (chk[j][i] == true) {
                    cnt++;
                    continue;
                }
                temp.add(map[j][i]);
            }

            for (int j = M - 1, k = 0; j >= 0; j--, k++) {
                /**
                 * k : 현재의 행
                 * temp.size() : 블록이 떨어져 생긴 열의 리스트 개수
                 * 문자를 맵에 갱신 해준다
                 */
                if (k < temp.size())
                    map[j][i] = temp.get(k);
                else 
                    map[j][i] = '0'; // 떨어져서 문자가 없다
            }
        }
        return cnt;
    }

떨어지는 블록이기 때문에 체크된 부분 이하의 index는 은 떨어져서 문자가 존재 하지 않을 것이기 때문에 '0' 으로 설정 해준다. 마지막 행부터 검사하는 이유도 그것 때문이다 temp 리스트는 제일 하위에 있는 블록 부터 제일 상단의 있는 블록까지 순서대로 재 갱신하는데 사용되게 되고 그것이 갱신된 리스트의 개수가 k 보다 클때까지 temp를 옮겨줌으로서 map을 재갱신 할 수 있다
만약 리스트의 개수가 k보다 작게 된다고 하면 떨어져서 아무것도 존재 하지 않는 블록이다.

문제 어렵다. 그래프 문제 너무 오래간만인듯
문제를 많이 풀어봐야 겠다

전체 코드

전체 코드