문제 접근하기
https://school.programmers.co.kr/learn/courses/30/lessons/17679
프렌즈 4블록문제는 구현 문제이다. 다음은 프렌즈 4블록 문제를 풀기 위해서 구현해야 목록이다.
- block을 수정 가능한 2차원 배열 형태로 만든다.
- 4각형(4개의 블록)이 모두 일치하면 제거한다. 그러나 인접한 블록을 이용해서 다른 블록도 지울 수 있는 경우 함께 지운다.
- 지운 블록을 카운트한다.
- 지운 블록이 0이 될 때까지 반복한다.
이 문제가 까다로운 이유는 2번 과정 때문이다. 블록을 제거해야 하지만 인접한 블록을 모두 제거하고 카운트해야 하기 때문에 단순히 실시간으로 지우는 방법으로는 문제를 풀 수 없다.
그래서 2번 3번은 구현하기 위해서 지울 좌표 목록을 저장해두고 한번에 삭제하며 카운트 해야한다.
그리고, 지울 때 테트리스 같이 지운후 블록이 내려가야 한다.
삭제하고 빈 내용은 위로 빼고, 나머지는 밑으로 모두 쉬프트해줘야한다. 이 문제의 변별력은 2 - 3 번 과정에서 삭제와 쉬프트를 구현할 수 있는가에 달려있다.
문제 풀이
문제를 푸는 데는 여러가지 접근 방법이 있지만 2가지 방법으로 풀어보려고 한다.
- 쉬프트 알고리즘을 설계하고 활용한다.
- 쉬프트를 쉽게 수행하기 위해 배열을 재구성한다.
1. 쉬프트 알고리즘 설계후 활용하는 방법
위에서 삭제된 정보는 위에 배치하고 나머지 자료들은 아래로 밀어야한다. 이것은 문제를 간단하게 만들면 다음과 같다.
"12@@34@@56" 문자열이 존재하는데 "123456@@@@" 로 만들도록 코드를 짜는 것이다.
이 방법은 다음과 같은 접근 방법으로 해결할 수 있다.
class Solution {
private static final char EMPTY = '@';
public String shift(String input) {
char[] chars = input.toCharArray();
int writeIndex = 0;
for (int i = 0; i < input.length(); ++i) {
if (chars[i] != EMPTY) {
chars[writeIndex++] = chars[i];
}
}
for (int i = writeIndex; i < input.length(); ++i) {
chars[i] = EMPTY;
}
return String.valueOf(chars);
}
}그런데 문제는 4블록 문제의 경우 위로 쌓이는데 위로 쌓인다는 말은 좌표 0에 가깝게 쌓인다는 의미로 위에서 구현한 shift가 역으로 동작해야 한다. 이 또한 위의 알고리즘을 활용해 간단하게 구현할 수 있다.
public String reverseShift(String input) {
char[] chars = input.toCharArray();
int writeIndex = input.length() - 1;
for (int i = writeIndex; i >= 0; i--) {
if (chars[i] != EMPTY) {
chars[writeIndex--] = chars[i];
}
}
for (int i = 0; i <= writeIndex; ++i) {
chars[i] = EMPTY;
}
return String.valueOf(chars);
}이 코드를 활용해서 프렌즈 4블록 문제를 풀어보자
public int solution(int m, int n, String[] board) {
// board를 수정 가능한 2차원 형태의 배열로 변환
char[][] newBoard = makeBoard(m, n, board);
int cnt = 0;
while (true) {
// 블록 삭제
int deleteCount = deleteBlock(m, n, newBoard);
// 삭제된 블록 쉬프트
gravityShift(m, n, newBoard);
// 탈출 조건
if (deleteCount == 0) {
break;
}
// 매번 블록 삭제마다 삭제된 블록 갯수 누적
cnt += deleteCount;
}
return cnt;
}makeBoard는 너무 간단하므로 생략하고
deleteBlock부터 살펴보자
private int deleteBlock(int m, int n, char[][] board) {
Set<Point> deletePoints = new HashSet<>();
for (int i = 0; i < m - 1; ++i) {
for (int j = 0; j < n - 1; ++j) {
if (board[i][j] != EMPTY && isSameSquare(i, j, board)) {
deletePoints.add(new Point(i, j));
deletePoints.add(new Point(i, j + 1));
deletePoints.add(new Point(i + 1, j));
deletePoints.add(new Point(i + 1, j + 1));
}
}
}
for (Point deletePoint : deletePoints) {
board[deletePoint.y][deletePoint.x] = EMPTY;
}
return deletePoints.size();
}여기서 Point 객체는 (y, x)를 담을 좌표 객체이다. value object 형태로 만들어주면 된다.(final, equals and hashcode 사용해서 객체 생성)
위와 같이 코드를 짠 이유는 실시간 삭제를 하면 문제대로 구현할 수 없기 때문에 4개가 서로 붙어있는 경우의 중복 문제를 풀 수 없다. 그렇기에 Set에 저장해두고 한꺼번에 삭제하는 것이다.
gravityShift를 살펴보자.
private void gravityShift(int m, int n, char[][] board) {
for (int j = 0; j < n; ++j) {
int writeIndex = m - 1;
for (int i = m - 1; i >= 0; --i) {
if (board[i][j] != EMPTY) {
board[writeIndex--][j] = board[i][j];
}
}
for (int i = writeIndex; i >= 0; --i) {
board[i][j] = EMPTY;
}
}
}gravityShift는 이전에 reverseShift 알고리즘 구현과 사실상 똑같고 가로 대신 세로로 진행된다는 차이점만 있다. 이런 재료들을 잘 조합하면 문제를 쉽게 풀 수 있다.
다음은 전체 코드이다.
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
class Solution {
private static final char EMPTY = ' ';
public int solution(int m, int n, String[] board) {
char[][] newBoard = makeBoard(m, n, board);
int cnt = 0;
while (true) {
int deleteCount = deleteBlock(m, n, newBoard);
if (deleteCount == 0) {
break;
}
cnt += deleteCount;
gravityShift(m, n, newBoard);
}
return cnt;
}
private char[][] makeBoard(int m, int n, String[] board) {
char[][] newBoard = new char[m][n];
for (int i = 0; i < m; i++) {
newBoard[i] = board[i].toCharArray();
}
return newBoard;
}
private int deleteBlock(int m, int n, char[][] board) {
Set<Point> deletePoints = new HashSet<>();
for (int i = 0; i < m - 1; ++i) {
for (int j = 0; j < n - 1; ++j) {
if (board[i][j] != EMPTY && isSameSquare(i, j, board)) {
deletePoints.add(new Point(i, j));
deletePoints.add(new Point(i, j + 1));
deletePoints.add(new Point(i + 1, j));
deletePoints.add(new Point(i + 1, j + 1));
}
}
}
for (Point deletePoint : deletePoints) {
board[deletePoint.y][deletePoint.x] = EMPTY;
}
return deletePoints.size();
}
private void gravityShift(int m, int n, char[][] board) {
for (int j = 0; j < n; ++j) {
int writeIndex = m - 1;
for (int i = m - 1; i >= 0; --i) {
if (board[i][j] != EMPTY) {
board[writeIndex--][j] = board[i][j];
}
}
for (int i = writeIndex; i >= 0; --i) {
board[i][j] = EMPTY;
}
}
}
private boolean isSameSquare(int y, int x, char[][] board) {
return board[y][x] == board[y][x + 1]
&& board[y][x] == board[y + 1][x]
&& board[y][x] == board[y + 1][x + 1];
}
static class Point {
private final int y;
private final int x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Point point = (Point) o;
return y == point.y && x == point.x;
}
@Override
public int hashCode() {
return Objects.hash(y, x);
}
}
}2. 쉬프트를 쉽게 수행하기 위해 배열을 재구성하는 방법
이 방법은 자바보다는 python에서 좀 더 쉬운 방법이다. python에서 제공하는 함수들을 이용해 배열을 재생성하고 filtering 처리해서 재배열한다. 이 방법은 매번 인스턴스를 생성하기 때문에 1번보다는 Performance가 좋지 못하다. 그럼 시작해보자.
def solution(m, n, board):
# 시계 방향으로 90도 회전
new_board = list(map(list, zip(*board[::-1])))
cnt = 0
while True:
count = delete_block(m, n, new_board)
if count == 0:
break
cnt += count
return cnt이 문제 풀이의 핵심은 배열을 90도 회전시키는 것에 있다. 위 문제의 쉬프트는 2차원 배열에서 아래 방향으로 동작한다. 그리고 비어있는 배열값은 위로 빠진다. 이것을 90도 회전된 배열에서 살펴보면 비어있는 값은 오른쪽으로, 비어있지 않은 값은 왼쪽으로 이동한다. 왼쪽 오른쪽으로 이동은 2차원 배열에서는 동일 배열에서 움직이는 것이므로 배열의 재정의하거나 컨트롤하기가 쉬워진다.
이제 변환된 board의 블록을 삭제하는 로직을 살펴보자
def delete_block(m, n, new_board):
# 사각형 모양 삭제할 좌표 찾아서 저장하기
delete_set = set()
for i in range(n - 1):
for j in range(m - 1):
if new_board[i][j] != "@" and is_square_same(i, j, new_board):
delete_set.update([(i, j), (i, j + 1), (i + 1, j), (i + 1, j + 1)])
# 삭제 상태로 바꾸기
for y, x in delete_set:
new_board[y][x] = "@"
# "@"을 오른쪽에 밀고 나머지는 filtering해서 왼쪽으로 밀어넣기
for i, row in enumerate(new_board):
empty = ["@"] * row.count("@")
new_board[i] = [r for r in row if r != "@"] + empty
return len(delete_set)윗 부분은 첫번쨰 풀이와 동일하고 아래를 살펴보면 "@" 갯수를 세준다. 그리고 new_board[i] 의 배열을 리스트 컨프리핸션과 필터를 이용해 재구성해준다. 이를 활용해서 새로운 리스트를 생성해준다.
최종 코드는 다음과 같다.
def is_square_same(i, j, board):
return board[i][j] == board[i][j + 1] == board[i + 1][j] == board[i + 1][j + 1]
def delete_block(m, n, new_board):
delete_set = set()
for i in range(n - 1):
for j in range(m - 1):
if new_board[i][j] != "@" and is_square_same(i, j, new_board):
delete_set.update([(i, j), (i, j + 1), (i + 1, j), (i + 1, j + 1)])
for y, x in delete_set:
new_board[y][x] = "@"
for i, row in enumerate(new_board):
empty = ["@"] * row.count("@")
new_board[i] = [r for r in row if r != "@"] + empty
return len(delete_set)
def solution(m, n, board):
new_board = list(map(list, zip(*board[::-1])))
cnt = 0
while True:
count = delete_block(m, n, new_board)
if count == 0:
break
cnt += count
return cnt