[JAVA] 프로그래머스 - [1차] 프렌즈4블록 - lv2

문제내용

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

코딩테스트 연습 - [1차] 프렌즈4블록

프렌즈4블록

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈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가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

 

---

문제 접근 방법

간단하게 생각하면된다.  블록지우고 -> 검사하고 -> 지워졌다면 -> 블록 내리고 -> 다시 반복....

이런 과정을 거치면서 블록을 하나 지울때마다 카운트를 증가시켜주면 답이된다. 이과정을 좀 자세히 말해보면

 

1. 블록 지우기

i행 j열을 시작으로 2x2블록 즉, (i, j) (i, j+1) (i+1, j+1) (i+1, j) 가 같은 블록인지 확인하고 같은 블록이라면 일단 이들의 위치를 저장해준다. 이유는 2x2블록이 겹칠수도 있기 때문.

이후에 마지막까지 탐색을 마쳤을때 저장했던 위치들을 하나씩 뽑으면서 블록을 지우고, 지울때마다 카운트를 증가시킨다.

 

2. 검사하기.(반복문 중단 조건)

이건 간단하게 만약 1번에서 블록이 지워지지 않았으면 즉, 카운트가 증가된게 없다면 반복문을 중단하면된다.

 

3. 블록 내리기

가장 왼쪽 열부터 시작해서 가장 마지막 행부터 차례대로 0행까지 쭉~ 탐색한다.

탐색하면서 빈공간이 있으면 space 변수를 증가시켜주고, 블록이 나왔을때 space가 0이 아니라면 이전에 빈공간이 있었단 뜻이므로 이전 행 i+space 에 있는 빈 공간을 현재 행 i 에 있는 블록을 바꿔주고 현재 행 i 에는 빈공간을 넣어주면된다.

 

---

풀이

import java.util.HashSet;
import java.util.Iterator;

public class Solution {
	static private char[][] arr;
	static private int answer=0;
	static private class Vertex{
		int x, y;
		public Vertex(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
    
    public static int solution(int m, int n, String[] board) {
        arr = new char[m][n];
        for(int i=0; i<board.length; i++) {
        	char[] temp = board[i].toCharArray();
        	for(int j=0; j<temp.length; j++) {
        		arr[i][j] = temp[j];
        	}
        }
        
        while(true) {
        	//2x2되는 블록들 전부 지우고 검사하기
        	//검사는 블록이 지워졌는지 안지워졌는지 검사하는거.
        	//만약 안지워졌으면 false 반환 == 더이상 지울 블록이 없다
        	if(!removeAndCheck()) break;
        	downArr();//블록 내리기.
        }
        
        return answer;
    }
    
    //블록 삭제 및 검사
    public static boolean removeAndCheck() {
    	int cnt=0;//이번턴에 지운 블록개수
    	HashSet<Vertex> set = new HashSet<>();//지울 블록들 위치 저장.
    	
    	//첨부터끝까지 2x2 블록있는 탐색.
    	for(int i=0; i<arr.length-1; i++) {
    		for(int j=0; j<arr[0].length-1; j++) {
    			if(arr[i][j]=='.') continue;//이미 지운블록 건너뜀.
    			//같은 블록들이 2x2를 이룰때 set에 위치 저장.
    			if(arr[i][j]==arr[i][j+1] && arr[i][j+1]==arr[i+1][j+1] && arr[i+1][j+1]==arr[i+1][j]) {
    				set.add(new Vertex(i,j));
    				set.add(new Vertex(i,j+1));
    				set.add(new Vertex(i+1,j+1));
    				set.add(new Vertex(i+1,j));
    			}
    		}
    	}
    	
    	Iterator<Vertex> iter = set.iterator();
    	//저장된 위치가 있으면 하나씩 뽑으면서 블록삭제. + 카운트증가
    	while(iter.hasNext()) {
    		Vertex v = iter.next();
    		if(arr[v.x][v.y]=='.') continue;
    		else if(arr[v.x][v.y]!='.') {
    			cnt++;
    			arr[v.x][v.y]='.';
    		}
    	}
    	
    	answer+=cnt;
    	
    	if(cnt==0) return false;
    	return true;
    }
    
    //블록내리기.
    public static void downArr() {
    	//0열부터 탐색
    	for(int j=0; j<arr[0].length; j++) {
    		int space = 0;//중간에 비워져있는 공간 개수
    		for(int i=arr.length-1; i>=0; i--) {
    			//빈공간 나올때마다 space 증가.
    			if(arr[i][j]=='.') space++;
    			//블록이 있고, 이전에 빈공간이 있었다면 빈공간 만큼 블록 내리고 원래 위치는 빈공간으로. 
    			else if(arr[i][j]!='.' && space!=0) {
    				arr[i+space][j]=arr[i][j];
    				arr[i][j]='.';
    			}
    		}
    	}
    }
}

---

마치며

이번 문제는 특별한 알고리즘 없이 그냥 단순히 배열을 조작하는 문제라고 생각하면 된다. 크게 설명이 필요한 문제는 아닌듯 하다. 근데 프로그래머스에서 해설보러가기 보니깐 카카오에서 이문제 난이도를 상으로 분류해놨는데,, 한단계 낮은 난이도가 개인적으로 3배는 어렵다 ;;