[프로그래머스] [1차] 프렌즈4블록 (level2, python)

문제 설명

 

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈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)을 의미한다

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

---

입력 형식

 

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

---

출력 형식

 

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

---

입출력 예제

---

예제에 대한 설명

 

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

---

풀이 코드

def check(m, n, board):
    filter = [[0 for _ in range(n)] for _ in range(m)]
    count = 0
    
    # check can delete
    for i in range(m-1):
        for j in range(n-1):
            a = board[i][j]
            b = board[i][j+1]
            c = board[i+1][j]
            d = board[i+1][j+1]
            if a == b == c == d and a != '0':
                filter[i][j], filter[i][j+1], filter[i+1][j], filter[i+1][j+1] = 1, 1, 1, 1
    
    for i in range(m):
        for j in range(n):
            if filter[i][j] == 1:
                count += 1
                board[i][j] = '0'
    
    if count == 0:
        return 0
    
    # fill blank
    for i in range(m-2, -1, -1):
        for j in range(n):
            k = i
            while 0 <= k+1 < m and board[k+1][j] == '0':
                k += 1
            if k != i:
                board[k][j] = board[i][j]
                board[i][j] = '0'
                
    return count

def solution(m, n, board):
    answer = 0
    board = list(map(list, board))
    
    while True:
        temp = check(m, n, board)
        if temp == 0:
            break
        answer += temp
        
    return answer

구현 문제이다.

 

처음 구현 문제를 접한 사람들은 어려울 수 있지만, 2048 문제를 한 번이라도 풀어본 적이 있거나, 백준 골드급 구현 문제나 삼성 기출을 많이 풀어본 사람들은 쉽게 풀 수 있을 것이다.

 

코드를 풀어서 보자.

board = list(map(list, board))

우선, 보드 리스트 내에 문자열로 저장이 되어있는데, 문자열 내부의 원소를 수정해야 할 일이 있다.

블록이 터진 후, 아래로 내려가야 하기 때문이다.

 

하지만 문자열 상태로 존재하면 인덱스로 접근해 값을 수정하기 어렵기 떄문에,

board를 2중 배열로 변환한다.

 

check 함수가 하는 역할은 다음과 같다.

1) 내부에 2x2 블록이 터질 것이 있는지 확인

2) 터질 수 있는 블록 board에 적용하고, 터진 블록의 갯수 세기

3) 터지고 남은 빈 공간에 대해 공백을 메꾸는 작업 후 board에 갱신

4) 터진 블록의 갯수 리턴

 

터질 수 있는 블록은 서로 겹칠 수 있는 상태이다.

2x2씩 계속 돌면서 그때 그때 터뜨리게 되면, 터질 수 있는 겹친 블록은 터지지 않게 반영될 수 있다.

시간 복잡도가 더 나오더라도, 터뜨릴 수 있는 블록에 대해서 filter 변수를 통해 마킹을 해놓고,

한 번에 터뜨린다.

 

이때 터뜨린 블록의 갯수를 세어놓는다.

 

블록을 제일 아래로 내리는 방법은,

제일 아래에서 두 번째 행부터 체크한다.

제일 아래는 내려갈 공간이 없기 때문이다.

 

자신의 블록 밑에 '0'으로 채워져있고, '0'이 아닌 것이 나오거나 바닥이 나올 때까지 k 값을 올려준다.

그 후, 밑에 내려갈 수 있는 상황이라면 값을 갱신해준다.

 

그 후 제일 아래에서 세번째 행, 네 번째 행 순으로 모두 갱신해주면 풀이할 수 있다.