알고리즘 분류: 구현
문제 설명:
블라인드 채용에 합격한 신입사원 Ryan은 새로운 게임 개발을 맡게 되었습니다.
이번에 등장하는 게임의 제목은 “프렌즈4블럭”입니다.
같은 모양의 카카오프렌즈 블록 4개를 2×2 모양으로 나란히 놓고 사라지면 점수를 얻는 게임입니다.
보드가 위와 같으면 2×2 사자 블록 7개와 2×2 원뿔 블록 4개가 제거됩니다.
동일한 블록이 여러 개의 2×2에 포함될 수 있으며 지우기 조건을 충족하는 2×2 모양이 여러 개 있으면 즉시 지워집니다.
블록이 지워지면 그 위에 있는 블록이 아래로 떨어져 빈 공간을 채웁니다.
빈 공간을 채운 후 같은 모양의 블록을 다시 2×2 모양으로 모으면 지워지고 다시 떨어집니다.
입력:
- 플레이트 높이 입력 m, 폭 n 및 플레이트 레이아웃 정보 브렛이 들어온다
- 2 ≦ N, 중 <30
- 보드 길이 n의 시퀀스 m 배열로 제공됩니다.
대문자 A부터 Z까지 블록을 나타내는 데 사용됩니다.
누르다 :
버전 정보가 주어지면 삭제할 블록 수를 입력으로 제공합니다.
해결책:
구현하는 데 오랜 시간이 걸리는 문제였습니다.
다만, 문제로 만든 요구사항은 간단했지만, 주의할 점이 두 가지 있었다.
첫 번째는 4개의 셀이 모두 동일하므로 깨지기 직전의 셀에 대해 오른쪽, 아래쪽 및 대각선 아래쪽을 확인해야 하고 두 번째는 이미 공백이 된 동일한 셀을 제외하는 것입니다.
코드가 길기 때문에 중간 처리 과정을 메소드로 추출하지 않으면 풀기가 너무 혼란스럽습니다.
그럼 프로세스별 방법으로 추출하여 해결해보자.
import java.util.*;
class Solution {
static class Block{
private int y;
private int x;
public Block(int y,int x){
this.y = y;
this.x = x;
}
}
static Deque<Block> q;
static char()() friends;
static int() dy = new int(){1,0,1};
static int() dx = new int(){0,1,1};
static int count;
static int mm;
static int nn;
public int solution(int m, int n, String() board) {
friends = new char(m)(n);
mm=m;
nn=n;
count = 0;
for(int i=0;i<m;i++){
String() split = board(i).split("");
for(int j=0;j<n;j++){
friends(i)(j)=split(j).charAt(0);
}
}
while(true){
q = new LinkedList<Block>();
findFriends();
if(q.isEmpty()){
break;
}
removeFriends();
pollFriends();
}
return count;
}
private static void findFriends(){
for(int i=0;i<mm-1;i++){
for(int j=0;j<nn-1;j++){
char c = friends(i)(j);
if(c!
='0'){
boolean flag=true;
for(int k=0;k<3;k++){
int yy=i+dy(k);
int xx=j+dx(k);
if(0<=yy && yy<mm && 0<=xx && xx<nn && friends(yy)(xx)==c){
continue;
}else{
flag = false;
break;
}
}
if(flag){
q.add(new Block(i,j));
}
}
}
}
}
private static void removeFriends(){
while(!
q.isEmpty()){
Block block =q.poll();
int y = block.y;
int x = block.x;
if(friends(y)(x)!
='0'){
count++;
friends(y)(x)='0';
}
for(int i=0;i<3;i++){
int yy = y+dy(i);
int xx = x+dx(i);
if(friends(yy)(xx)!
='0'){
count++;
friends(yy)(xx)='0';
}
}
}
}
private static void pollFriends(){
for(int i=0;i<nn;i++){
for(int j=mm-1;j>=0;j--){
if (friends(j)(i)!
='0'){
int zeroindex=j+1;
while(zeroindex<mm){
if(friends(zeroindex)(i)=='0'){
char c = friends(zeroindex-1)(i);
friends(zeroindex)(i)=c;
friends(zeroindex-1)(i)='0';
zeroindex++;
}
else{
break;
}
}
}
}
}
}
}