[알고리즘] 프로그래머스 [1차] 프렌즈4 블록 -2018 KAKAO BLIND RECRUITMENT-

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

프로그래머스

 

 

 

 

프로그래머스 프렌즈4 블록 문제를 풀어봤습니다. ㅎㅎ

처음에 기존의 단순 BFS 문제처럼 bfs 함수를 만들고 큐와 while 반복문을 통해 풀려고 했는데 풀다가 아닌 것 같아 지우고 다시 풀었네요.

그런데 블록을 재배치하는 함수인 arrange() 에서 queue.offer(j) 를 i로 바꿔써서 이거 못찾아서 시간을 많이 잡아먹었습니다. ㅠㅠ (신기한게 실행 테스트케이스는 맞는데 제출하기 테스트케이스가 3개 틀려서 무슨 특이케이스가 있거나 뭘 빼먹었는지 한참 찾았습니다...)

 

BFS 의 문제에서 자주쓰던 동서남북 탐색하는 로직이 필요했고 다음과 같은 경우의 수를 주의해야했습니다. (isVisited 로 구분!)

 

 

 

풀이 방법을 정리하면 다음과 같습니다.

1. 터지는 블록이 없을 때 까지 반복한다.

while (true) { //터지는 폭탄이 없을때 까지 반복
            isVisited = new boolean[m][n];
            isBombFlag = false;
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    checkBomb(i, j);
                }
            }
            changeBomb();
            if (!isBombFlag) { //터진 폭탄없으면 끝
                break;
            }
            arrange();
        }
        return answer;

 

 

2. 2x2 같은 블록이면 터지는거니까 자신의 위치에서 우,하, 오른쪽아래대각선 만 탐색하면된다. 그래서 n-1, m-1 만큼만 반복문을 돌린다.

private static int[] dx = {0, 1, 0, 1};
    private static int[] dy = {0, 0, 1, 1};

 

 

3. checkBomb() 현재 블록에서 2x2 탐색을 하여 모두 같은 블록인지 탐색한다. 전부 같다면 그 블록들 개수 만큼 터트린 개수(answer)을 증가시키고 해당 블록의 isVisited true로 해준다. 그리고 터진 폭탄이 있다는 것을 알려주기 위해 전역변수인 isBombFlag 를 true로 해준다.

// 2x2 터질 곳 있는지 체크
    public static boolean checkBomb(int x, int y) {
        char block = map[x][y];
        if (block == '0') {
            return false;
        }
        for (int i = 0; i < 4; i++) {
            int x2 = x + dx[i];
            int y2 = y + dy[i];
            if (block != map[x2][y2]) {
                return false;
            }
        }
        isBombFlag = true; // 터트릴수 있음
        for (int i = 0; i < 4; i++) { //이미 터트린 폭탄을 제외한 2x2 폭탄 제거
            int x2 = x + dx[i];
            int y2 = y + dy[i];
            if (!isVisited[x2][y2]) {
                answer++; // 제거 개수 추가
            }
            isVisited[x2][y2] = true;
        }
        return true;
    }

 

 

4. 전체 맵을 다 탐색후 터진 블록의 값을 0으로 바꿔준다.

// 터진 곳 폭탄 값으로 변경
    public static void changeBomb() {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isVisited[i][j]) {
                    map[i][j] = '0';
                }
            }
        }
    }

 

 

 

5. 터진 폭탄이 없으면 반복문을 끝낸다.

if (!isBombFlag) { //터진 폭탄없으면 끝
                break;
            }

 

 

6. 터진 폭탄이 있다면 폭탄이 터진곳의 위에 있는 블록들이 내려오게 재조정 해줘야한다. 세로줄로 하나씩 불러와서 폭탄이 아닌 값을 각각의 큐에 넣고 리스트에 담아주고 다시 맵에 차례대로 블록들을 넣어준다.

// 폭탄으로 인한 맵 조정
    public static void arrange() {
        ArrayList<Queue> list = new ArrayList<>();
        // 한줄 세로로 아래에서 위 순으로 프렌즈블록만 하나씩 불러옴
        for (int j = 0; j < n; j++) {
            // 처음에 이걸 리스트에 list 밑에 생성하고 이부분에 queue.clear() 하는 식으로 했는데
            // 그러면 list에 이미 들어가 있는 큐도 똑같이 값이 바뀌어 이상해진다. (얕은복사여서 그렇다 주의)
            Queue<Character> queue = new LinkedList();
            for (int i = m - 1; i >= 0; i--) {
                if (map[i][j] != '0') { //폭탄아니면 큐에 삽입
                    queue.offer(map[i][j]);
                }
            }
            list.add(queue);
        }
        // 맵 재조정
        for (int j = 0; j < n; j++) {
            for (int i = m - 1; i >= 0; i--) {
                Queue queue2 = list.get(j);
                if (!queue2.isEmpty()) {
                    map[i][j] = (char) queue2.poll();
                } else {
                    map[i][j] = '0';
                }
            }
        }
    }

 

 

 

 

 

[풀이는 다음과 같습니다.]

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public static char[][] map;
    public static boolean[][] isVisited;
    public static int answer = 0;
    public static int m;
    public static int n;
    static boolean isBombFlag;
    private static int[] dx = {0, 1, 0, 1};
    private static int[] dy = {0, 0, 1, 1};

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(3, 2, new String[]{"AA", "AA", "AB"});
    }

    // 2x2 터질 곳 있는지 체크
    public static boolean checkBomb(int x, int y) {
        char block = map[x][y];
        if (block == '0') {
            return false;
        }
        for (int i = 0; i < 4; i++) {
            int x2 = x + dx[i];
            int y2 = y + dy[i];
            if (block != map[x2][y2]) {
                return false;
            }
        }
        isBombFlag = true; // 터트릴수 있음
        for (int i = 0; i < 4; i++) { //이미 터트린 폭탄을 제외한 2x2 폭탄 제거
            int x2 = x + dx[i];
            int y2 = y + dy[i];
            if (!isVisited[x2][y2]) {
                answer++; // 제거 개수 추가
            }
            isVisited[x2][y2] = true;
        }
        return true;
    }

    // 터진 곳 폭탄 값으로 변경
    public static void changeBomb() {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isVisited[i][j]) {
                    map[i][j] = '0';
                }
            }
        }
    }

    // 폭탄으로 인한 맵 조정
    public static void arrange() {
        ArrayList<Queue> list = new ArrayList<>();
        // 한줄 세로로 아래에서 위 순으로 프렌즈블록만 하나씩 불러옴
        for (int j = 0; j < n; j++) {
            // 처음에 이걸 리스트에 list 밑에 생성하고 이부분에 queue.clear() 하는 식으로 했는데
            // 그러면 list에 이미 들어가 있는 큐도 똑같이 값이 바뀌어 이상해진다. (얕은복사여서 그렇다 주의)
            Queue<Character> queue = new LinkedList();
            for (int i = m - 1; i >= 0; i--) {
                if (map[i][j] != '0') { //폭탄아니면 큐에 삽입
                    queue.offer(map[i][j]);
                }
            }
            list.add(queue);
        }
        // 맵 재조정
        for (int j = 0; j < n; j++) {
            for (int i = m - 1; i >= 0; i--) {
                Queue queue2 = list.get(j);
                if (!queue2.isEmpty()) {
                    map[i][j] = (char) queue2.poll();
                } else {
                    map[i][j] = '0';
                }
            }
        }
    }

    public int solution(int m, int n, String[] board) {
        Solution.m = m;
        Solution.n = n;
        map = new char[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = board[i].charAt(j);
            }
        }
        while (true) { //터지는 폭탄이 없을때 까지 반복
            isVisited = new boolean[m][n];
            isBombFlag = false;
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    checkBomb(i, j);
                }
            }
            changeBomb();
            if (!isBombFlag) { //터진 폭탄없으면 끝
                break;
            }
            arrange();
        }
        return answer;
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다!