프렌즈4 블록

nelljun_kim·2022년 3월 20일
0

코딩테스트

목록 보기
1/8
post-thumbnail

처음 풀이

  1. 삭제할 블록 체크
  2. 블록 삭제
  3. 블록 이동

이 세 과정을 더 이상 삭제할 블록이 없을 때까지 반복하면 된다.

//각 글자를 요소로 할 2차원 배열
char[][] gameBoard;
//사이클마다, 삭제할 2x2 블록의 첫 번째 원소의 좌표 담을 set
Set<int[]> set = new HashSet<>();
//삭제되는 블록의 갯수
int count;

public int solution(int m, int n, String[] board) {
    //m x n 사이즈의 2차원 배열 생성
    gameBoard = new char[m][n];

    //게임 보드 알파벳 채우기
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            gameBoard[i][j] = board[i].charAt(j);
        }//for end
    }//for end

    while(true) {
        //삭제할 블록 있는지 체크(set에 블록 좌표 add)
        check(m, n);

        if(!set.isEmpty()) {
            //삭제할 블록 있는 경우
            //해당 위치의 배열 요소 값 ' ' 으로 초기화
            delete();
            //삭제된 블록 자리 메꾸기
            move(m, n);
        } else {
            //더 이상 삭제할 블록이 없는 경우
            break;
        }//if~else end
    }//while end

    return count;
}//solution() end

1. 삭제할 블록 체크

  • gameBoard 탐색하면서 [i][j], [i][j+1], [i+1][j], [i+1][j+1] 위치 값이 다 같다면 set에 int 배열로 {i, j}를 저장한다.
public static void check(int m, int n) {
    //매 사이클마다 set 초기화해준다.
    set.clear();

    for (int i = 0; i < m-1; i++) {
        for (int j = 0; j < n-1; j++) {
            //사이클이 돌아 빈 블록인 경우
            //continue
            if(gameBoard[i][j]==' ') continue;
            if(gameBoard[i][j]==gameBoard[i][j+1]
                    && gameBoard[i][j]==gameBoard[i+1][j]
                    && gameBoard[i][j]==gameBoard[i+1][j+1]) {
                set.add(new int[]{i, j});
            }//if end
        }//for end
    }//for end
}//check() end

2. 블록 삭제

  • set에 있는 대표 좌표를 중심으로 4좌표 모두 초기화한다.
  • 블록들끼리 겹치는 부분을 조심해서 count한다.
public static void delete() {
    Iterator<int[]> iterator = set.iterator();

    while(iterator.hasNext()) {
        int[] location = iterator.next();

        //2x2블록의 대표 좌표 중심으로 4좌표 모두 ' '로 초기화
        //블록들이 겹치는 부분은 한 번만 카운트 한다.
        if(gameBoard[location[0]][location[1]]!=' ') {
            gameBoard[location[0]][location[1]] = ' ';
            count++;
        }
        if(gameBoard[location[0]][location[1]+1]!=' ') {
            gameBoard[location[0]][location[1]+1] = ' ';
            count++;
        }
        if(gameBoard[location[0]+1][location[1]]!=' ') {
            gameBoard[location[0]+1][location[1]] = ' ';
            count++;
        }
        if(gameBoard[location[0]+1][location[1]+1]!=' ') {
            gameBoard[location[0]+1][location[1]+1] = ' ';
            count++;
        }
    }//while end
}//delete() end

3. 블록 이동

  • 아랫줄에서부터 빈 블럭을 채워나간다.
public static void move(int m, int n) {
    //아래서부터 채워야 하므로 마지막 row부터 탐색
    for (int i = m-1; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            if(gameBoard[i][j]==' ') {
                //빈 블록일 때
                //현재 위치[i][j]서부터 위로 올라가면서
                //비지 않은 블록의 값으로 현재 위치의 블록을 채우고
                //값을 가져온 블록은 ' '로 비운다.
                for (int k = i; k >= 0 ; k--) {
                    if(gameBoard[k][j]!=' ') {
                        gameBoard[i][j] = gameBoard[k][j];
                        gameBoard[k][j] = ' ';
                        break;
                    }//if end
                }//for end
            }//if end
        }//for end
    }//for end
}//move() end

다른 풀이

  • Set을 활용하여 삭제할 2x2 블록의 대표 좌표가 아닌 모든 좌표를 Point 클래스의 객체로 저장한다.
  • HashSet이, Point의 row와 column 필드값이 같다면 같은 Point 객체로 판단할 수 있도록 hashcode()와 equals()를 오버라이딩 해준다.
  • 따라서, 중복된 좌표는 Set에 두 번 저장하지 않는다.

Point 클래스

static class Point {
    int row;
    int column;

    public Point(int row, int column) {
        this.row = row;
        this.column = column;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj instanceof Point) {
            Point point = (Point) obj;
            return (point.row == this.row)
            		&& (point.column == this.column);
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return Objects.hash(row, column);
    }

}

check()

  • 삭제할 모든 블록의 좌표(Point)를 Set에 저장한다.
pointSet.add(new Point(i, j));
pointSet.add(new Point(i, j+1));
pointSet.add(new Point(i+1, j));
pointSet.add(new Point(i+1, j+1));

solution()

  • 매 사이클마다 Set의 사이즈가 곧 삭제된 블록의 갯수이다.
while(true) {
    check(m, n);

    if(!set.isEmpty()) {
        //set의 사이즈 = 삭제할 블록 갯수
        count += set.size();
        delete();
        move(m, n);
    } else {
        break;
    }//if~else end
}//while end

delete()

  • 삭제할 모든 블록이 Set에 저장되어있다. iterator로 Set 탐색하면서 gameBoard의 해당 위치 값 ' '로 초기화
while(iterator.hasNext()) {
    Point point = iterator.next();
    gameBoard[point.row][point.column] = ' ';
}//while end
profile
세상을 다양하게 하는 개발자

0개의 댓글