(해결완료) 프로그래머스 17679 - 프렌즈4블록

https://programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록

문제 설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT RRFACC RRRFCC TRRRAA TTMMMF TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

 

---

문제 풀이

처음에는 5,6번만 틀렸는데 하나의 테스트케이스를 더 해결하고 해보니 하나가 더 틀린다....

def check(m, n, board):
    position = []
    for i in range(m - 1):
        for j in range(n - 1):
            orig, down, right, cross = board[i][j], board[i + 1][j], board[i][j + 1], board[i + 1][j + 1]

            # 2*2 부분이 모두 동일하고 0이 아닐 때 배열에 추가(제거과정)
            if orig == down == right == cross:
                if orig != '0' and down != '0' and right != '0' and cross != '0':
                    # 중복 체크
                    if not [i, j] in position:
                        position.append([i, j])
                    if not [i + 1, j] in position:
                        position.append([i + 1, j])
                    if not [i, j + 1] in position:
                        position.append([i, j + 1])
                    if not [i + 1, j + 1] in position:
                        position.append([i + 1, j + 1])

    # 제거한 부분을 0으로 채우기
    for i in position:
        board[i[0]][i[1]] = '0'

    # 아래쪽부터 체크해서 밑으로 내리기
    for i in range(m - 2, -1, -1):
        for j in range(n - 1):
            if board[i][j] != '0' and board[i + 1][j] == '0':
                tmp = i
                while tmp <= m - 2 and board[tmp + 1][j] == '0':
                    board[tmp + 1][j] = board[tmp][j]
                    board[tmp][j] = '0'
                    tmp += 1

    return len(position)


def solution(m, n, board):
    answer = 0
    board = [list(board[i]) for i in range(m)]

    while True:
        temp = check(m, n, board)
        if temp == 0:
            break
        else:
            answer += temp

    return answer

 

---

최근에 면접도 잘 안되서 번아웃이 왔었는데 다시 마음잡고 풀었다.

몇가지 과정을 거치고 여러가지 테스트케이스를 거치면서 오류를 발견하였다.

 

CC
00
00
CC

 

이런 상황에서 맨 위에있는 C를 아래로 내려야 되는데 하나밖에 내려오지 않았다. 여기가 문제였다.

수정 전 / 수정 후 코드

지금보니 j의 범위가 이상하다. n = 2일 때, j는 0과 1이 들어가야되지만 0만 들어가고 끝난다.

그리고 아래의 if문에서 왜 and를 썼는지 지금 모르겠다.

 

해결코드

def check(m, n, board):
    position = []                   # 삭제될 위치의 좌표를 저장하는 배열
    for i in range(m - 1):
        for j in range(n - 1):
            orig, down, right, cross = board[i][j], board[i + 1][j], board[i][j + 1], board[i + 1][j + 1]
            # 본인, 아래, 옆, 대각선의 블럭을 저장
            
            if orig == down == right == cross:
                if orig != -1 and down != -1 and right != -1 and cross != -1:
                    if not [i, j] in position and orig >= 'A' and orig <= 'Z':
                        position.append([i, j])
                    if not [i + 1, j] in position and down >= 'A' and down <= 'Z':
                        position.append([i + 1, j])
                    if not [i, j + 1] in position and right >= 'A' and right <= 'Z':
                        position.append([i, j + 1])
                    if not [i + 1, j + 1] in position and cross >= 'A' and cross <= 'Z':
                        position.append([i + 1, j + 1])
    
    # 위에서 저장한 좌표를 제거
    for i in position:
        board[i[0]][i[1]] = -1

    # 남은 블럭들을 아래로 내리기
    for i in range(m - 2, -1, -1):
        for j in range(n):
            if board[i][j] != -1:
                tmp = i
                while tmp <= m - 2 and board[tmp + 1][j] == -1:
                    board[tmp + 1][j] = board[tmp][j]
                    board[tmp][j] = -1
                    tmp += 1

    return len(position)


def solution(m, n, board):
    answer = 0
    board = [list(board[i]) for i in range(m)]

    while True:
        temp = check(m, n, board)
        if temp == 0:
            break
        else:
            answer += temp

    return answer