프로그래머스 - 프렌즈 4블록

Lumi·2021년 12월 2일

알고리즘

목록 보기

45/59

function solution(m, n, board) {
  board = board.map((v) => v.split(""));
  let point = 0;

  while (true) {
    let arr = [];
    
    // 조건에 맞는 index값을 도출
    for (let i = 0; i < m - 1; i++) {
      for (let j = 0; j < n - 1; j++) {
        if (
          board[i][j] &&
          board[i][j] === board[i + 1][j] &&
          board[i][j] === board[i][j + 1] &&
          board[i][j] === board[i + 1][j + 1]
        ) {
          arr.push([i, j]);
        }
      }
    }

	// 정답 도출
    if (arr.length === 0) {
      for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
          if (board[i][j] === 0) {
            point++;
          }
        }
      }
      return point;
    }
    
	// 발견한 곳을 0으로 변경
    for (let i = 0; i < arr.length; i++) {
      let y = arr[i][0];
      let x = arr[i][1];
      board[y][x] = 0;
      board[y + 1][x] = 0;
      board[y][x + 1] = 0;
      board[y + 1][x + 1] = 0;
    }
	
    // 0으로 변경 완료하였기 떄문에 숫자를 떙겨줌
    for (let i = 1; i < m; i++) {
      for (let j = 0; j < n; j++) {
        if (board[i][j] === 0) {
          let temp = board[i - 1][j];
          board[i][j] = temp;
          board[i - 1][j] = 0;
        }
      }
    }
  }
}

일단 결론적으로는 아직 여러개의 테스트 중에서 두개가 통과가 안되었다 ㅠㅠ

내가 생각했던 로직은 이렇다.

일단 while문을 통해서 계속해서 값을 체크해 나간다.

[0,0]부터 비교를 해나가며

처음에 arr이라는 변수에 조건에 일치하는 값을 담게 된다.

이곳에서는 이제 특정 지점에서 다른 오른쪽, 아래, 오른쪽아래 부분이 같으면 삭제 대상인 것이다.
이런 문제는 DFS를 통해서도 해결 가능하다.

그후 지점이 발견되면 그곳을 0으로 바꾸어 준다.

0으로 바꾸는 것이 끝났으면 이제 위에서 아래로 숫자를 떙겨 주어야 한다.

이떄 우리는 y값만 움직이면 되기 떄문에 j값은 따로 건들지 않는다.

처음에 이런 상태라면

[ 'C', 'C', 'B', 'D', 'E' ]
[ 'A', 'A', 'A', 'D', 'E' ]
[ 'A', 'A', 'A', 'B', 'F' ]
[ 'C', 'C', 'B', 'B', 'F' ]

한번실행을 하면

[ 'C', 'C', 'B', 'D', 'E' ]
[ '0', '0', '0', 'D', 'E' ]
[ '0', '0', '0', 'B', 'F' ]
[ 'C', 'C', 'B', 'B', 'F' ]

이렇게 되고 그후 0의 위에있는 값들을 아래로 떙겨주게 되면


[ '0', '0', '0', 'D', 'E' ],
[ '0', '0', '0', 'D', 'E' ],
[ 'C', 'C', 'B', 'B', 'F' ],
[ 'C', 'C', 'B', 'B', 'F' ]

이렇게 변경이 되며 이 과정을 반복한다.

끝나는 지점은 arr에 더이상 아무런 값이 담기지 않을떄 이다.

그러면 이제 삭제할 곳이 없다는 것이기 떄문에

그러면 이제 board라는 2차원 배열에서 블록이 삭제된 갯수 즉 0의 갯수를 갱신한뒤에 return해주면 된다.

문제점을 발견 하였다.

문제는 바로 맨 아래 블록의 위치를 바꾸는 부분이다.

이 부분은 위에서 아래로 검사를 하지만 만약 맨 아랫부분에서 블록의 삭제가 이루어 준다면 정상적으로 작동하지 않게 된다.

그러기 떄문에 이 부분만 수정을 하면 된다.

이 부분은 3중 For문으로 해결을 하였다.

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;
          }
        }
      }
    }

우리는 일단 아래에서부터 검사를 해야 하며 이떄 블록이 0인 값들에 대해서만 검사를 해야 한다.

그 부분을 걸러주는 것이 첫번쨰 if문이다.