문제 설명
프렌즈4블록
블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.
만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.
블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.
만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.
위 초기 배치를 문자로 표시하면 아래와 같다.
각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.
입력 형식
입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
2 ≦ n, m ≦ 30
board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
출력 형식
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
예제에 대한 설명
입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.
function solution(m, n, board) {
board = board.map(v => v.split(''));
// board 배열의 각 문자열을 한 문자씩 분리하여 2차원 배열로 변환
while (true) {
let founded = [];
//무한루프 시작. 조건에 따라 루프를 빠져 나올 예정
//founded 배열은 제거할 블록의 위치를 저장할 배열
// 찾기
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (board[i][j] && board[i][j] === board[i][j - 1] && board[i][j] === board[i - 1][j - 1] && board[i][j] === board[i - 1][j]) {
founded.push([i, j]);
}
}
}
// 2중 for문을 사용하여 2x2 블록을 찾기
// 보드 배열 내에 인접한 2x2영역이 같은 문자로 구성되어 있다면, 해당 블록의 좌표를 founded에 추가
if (! founded.length) return [].concat(...board).filter(v => ! v).length;
//founded배열에 아무 값도 없다면, 더 이상 제거할 블록이 없는 상태이기 떄문에 남은 블록의 개수를 세서 반환.
// 부수기
founded.forEach(a => {
board[a[0]][a[1]] = 0;
board[a[0]][a[1] - 1] = 0;
board[a[0] - 1][a[1] - 1] = 0;
board[a[0] - 1][a[1]] = 0;
});
//founded에 저장된 블록의 위치를 이용하여 해당 블록을 제거
//제거한 블록의 위치에 해당하는 값들을 0으로 설정하여 제거
// [].concat(...board)는 board 배열의 모든 요소들을 1차원 배열로 합침
// .filter(v => !v)는 배열에서 빈 문자열 또는 falsy한 값을 제거. 즉, 남은 블록들만 남게 됨.
// 재정렬
for (let i = m - 1; i > 0; i--) {
if (! board[i].some(v => ! v))
continue;
for (let j = 0; j < n; j++) {
for (let k = i - 1; k >= 0 && ! board[i][j]; k--) {
if (board[k][j]) {
board[i][j] = board[k][j];
board[k][j] = 0;
break;
}
}
}
}
}
}
// 남은 블록들을 아래로 내리고 빈 공간을 채우는 과정
// 아래쪽부터 위로 순회하며 블록들을 아래로 내리고, 빈 공간을 위에서부터 채워넣기
시작부터,, 난감했다. 어떠한 방법으로 문제 풀이를 세울지 감이 안잡혔기 때문이다.
그렇기에 다른 사람의 풀이를 통해 한 줄 한 줄 분석하는 방향으로 하였다.
이 문제를 풀고 느낀 점은 .. 이게 ... LV2?라는 생각 뿐.. 카카오에서도 난이도 상으로 분류한 문제인데!! 정답률 17퍼센트인 문제인데 !! 그냥 ,, 내가 더 열심히 하자!
