[1차] 프렌즈4블록(Java)

🎯문제

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2�×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

입력 형식
입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
2 ≦ n, m ≦ 30
board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
출력 형식
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예제

m	n	board	answer
4	5	["CCBDE", "AAADE", "AAABF", "CCBBF"]	14
6	6	["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]	15

예제에 대한 설명 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다. 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

---

✏️풀이

코드

import java.util.*;

class Solution {
	// 삭제되는 블록의 수
    int answer;
	// 블록의 보드
    char[][] map;
    
	// 좌표 클래스
    class Point {
        int x, y;
        
        Point(int _x, int _y) {
            x = _x; y = _y;
        }
    }
    
	// 블록을 삭제하는 메서드
    public boolean remove() {
		// 삭제하는 블록을 저장할 Set
        Set<Point> set = new HashSet<>();
        
        for(int i = 0; i < map.length - 1; i++) {
            for(int j = 0; j < map[0].length - 1; j++) {
                // 이미 삭제된 블록은 넘어감
				if(map[i][j] == ' ') {
                    continue;
                }
				// 2*2 형태로 같은 블록이 모이면
                if(map[i][j] == map[i][j+1] && map[i][j] == map[i+1][j] && map[i][j] == map[i+1][j+1]) {
                    // Set에 값을 저장
					set.add(new Point(i, j));
                    set.add(new Point(i, j+1));
                    set.add(new Point(i+1, j));
                    set.add(new Point(i+1, j+1));
                }
            }
        }
        
		// Iterator를 사용해서 set에 있는 값을 가져옴
        Iterator<Point> iter = set.iterator();
		// 남아있는 값이 있을 경우 계속 반복
        while(iter.hasNext()) {
			// 해당 값을 변수에 따로 저장
            Point p = iter.next();
            
			// 이미 비워진 블록이면 넘어감
            if(map[p.x][p.y] == ' ') {
                continue;
            }
			// 블록을 비운 뒤 answer 증가
            map[p.x][p.y] = ' ';
            answer++;
        }
        
		// 저장된 값이 없을 경우 false, 저장된 값이 있을 경우 true
        return set.size() == 0 ? false : true;
    }
    
	// 블록을 내려주는 메서드
    public void blockdown() {
        for(int j = 0; j < map[0].length; j++) {
			// 비워진 부분을 저장
            int space = 0;
            for(int i = map.length - 1; i >= 0; i--) {
				// 비워진 블록이 존재하면 space 증가
                if(map[i][j] == ' ') {
                    space++;
                }
				// 블록이 비워져 있지 않으면서, 띄워져있다면 
				else if(map[i][j] != ' ' && space != 0) {
					// 값을 옮겨주고 해당 위치를 비워줌
                    map[i+space][j] = map[i][j];
                    map[i][j] = ' ';
                }
            }
        }
    }
    
    public int solution(int m, int n, String[] board) {
        answer = 0;
        map = new char[m][n];
        
		// map에 값을 저장
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                map[i][j] = board[i].charAt(j);
            }
        }
        
		// 제거된 값이 존재하면 반복
        while(remove()) {
			// 블록을 떨어뜨림
            blockdown();
        }
        
        return answer;
    }
}

설명

2차원 배열에 값을 저장한 뒤에 탐색을 진행하여 블록을 삭제하고 블록을 아래로 내리는 방법을 사용해서 문제를 해결하였다.

이때 탐색을 진행하여 블록을 삭제하는 메서드와 블록을 아래로 내리는 메서드를 직접 만들었다.

블록을 삭제하는 메서드를 먼저 살펴보면, HashSet을 사용해서 삭제하는 블록들을 저장했다. 처음부터 하나씩 탐색을 진행하는데 이미 삭제된 블록은 ' '로 처리를 했다. 이미 삭제된 블록은 탐색을 더이상 진행할 필요가 없으므로 continue를 사용해서 넘어가준다.
만약 2*2 형태로 같은 블록이 모인다면 Set에 값을 저장한다. 이때 Set을 사용하는 이유는 겹치는 블록들이 존재할 수 있기 때문이다. 따라서 Set을 통해서 중복을 자동으로 제거해주었다.
또한 Point라는 클래스를 사용해서 x, y 값을 한번에 저장할 수 있도록 해준다.
Iterator를 사용해서 Set에 있는 값들을 하나씩 가져온다. while문을 통해 모든 값을 하나씩 탐색하는데, 이미 삭제된 블록이라면 넘어가고 삭제된 블록이 아니라면 블록을 삭제한 뒤에 answer의 값을 증가시켜준다.
Set에 저장된 값이 없다면 삭제된 블록이 없다는 뜻이므로 false를, 저장된 값이 있다면 삭제된 블록이 있다는 뜻이므로 true를 반환해준다.

블록을 내려주는 메서드를 살펴보면, 열별로 탐색을 진행한다. 열별로 탐색을 진행한다는 것은 [0][0] -> [1][0] -> ... 처럼 앞의 값을 바꿔가면서 하나의 열씩 탐색을 진행해준다. 따라서 첫번째 for문에는 map[0].length의 길이만큼 반복을 진행한다.
space라는 변수를 통해 비워진 부분을 저장해준다. 비워진 부분을 저장해주어야 나중에 바꿔줄 위치를 찾아낼 수 있다.
두번째 for문에서 탐색을 밑에서부터 진행해준다. 즉 [3][0] -> [2][0] -> ... 이런 식으로 아래서부터 탐색을 진행하는 것이다. 이때 블록이 비워져있다면 space의 값을 증가시켜준다. 만약 블록이 비워져있지 않으면서 space에 값이 있다면 현재 위치가 블록이 띄워져있다는 뜻이 된다.
예를 들어, space = 1인데 [1][0]에 'T'가 있다면 [2][0]은 빈칸이라는 뜻이고, [3][0]에는 값이 있다는 뜻이다.
따라서 [1+space][0] = [2][0]에 [1][0]에 있는 값을 저장하고 [1][0]의 블록은 삭제한다.
위의 방식을 반복해서 블록을 아래로 내려준다.

while문을 통해 제거된 값이 없을 때까지 반복을 진행하고 제거된 값이 있다면 블록을 아래로 내려준 뒤에 다시 탐색을 진행한다.
위의 과정을 반복해서 반복문을 빠져나왔을 때 answer의 값을 반환해준다면 해결할 수 있다.

---

💡느낀 점

어떤 자료구조를 사용한 문제가 아니라 직접 메서드를 만들고 사용하는 문제여서 재밌게 풀 수 있었다. 자료구조 관련한 문제만 계속 풀다보니 숨겨진 어떤 공식이 있지 않을까 생각을 하다가 도저히 보이지 않아 직접 구현을 했는데 풀려서 이게 왜 됐지? 라는 생각이 들게 만드는 문제였다.

---

링크

문제 링크