18년도 카카오 블라인드 - 프렌즈 블록

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

프렌즈4블록

문제 설명

프렌즈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)을 의미한다

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

입력 형식

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

출력 형식

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

입출력 예제

mnboardanswer

4	5	["CCBDE", "AAADE", "AAABF", "CCBBF"]	14
6	6	["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]	15

예제에 대한 설명

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

---

[문제 설명]

 

1. 이 문제의 블록 제거 조건은 4개이상 그리고 네모 형태입니다. 때문에 bfs나 dfs로 탐색할 수 없습니다.

 

2. 저는 board를 오른쪽 => 왼쪽으로 탐색해서 사각형 + 4개이상이 있는지 탐색할 예정 입니다. 그렇기 때문에 좌표를 통해 탐색할 구간은 4개만 있으면 됩니다.

i, j를 기준으로 [i + 1, j], [i, j + 1], [i + 1, j + 1]

왜? 상하좌우를 탐색하지 않고 오른쪽 방향만 탐색하냐고 할 수 있습니다. 일단 저는 모든 좌표를 찾을 것이므로 이렇게 탐색해도 전구간에서 사각형이 되는 부분을 찾을 수 있기 때문입니다.

 

3. 그리고 탐색하면서 4각형 블록이 있다면 바로 표시해주는게 아니라 한 번에 board를 탐색 후 바꿀 것 입니다.

i, j 가 되는 좌표만 기억해놓을 것 입니다.

그리고 board를 탐색할 때마다 isChange 플레그 함수를 넣어서 한 번이라도 4블록을 찾으면 true로 설정. 없다면 false가 되서 board 탐색을 멈추고 종료 합니다.

 

4. 있다면 기억 해놓은 i,j 좌표를 기준으로 3방향을 -1로 만들어 주면 됩니다.

 

5. 여기까지 왔으면 board를 아래에서 돌면서 해당 좌표가 비어있으면 위로 올라가면서 비어있지 않는 좌표가 있다면 좌표를 스왑하는 형식으로 블럭을 내리는 작업을 구현합니다.

 

6. 이렇게 계속 돌다보면 board가 변화하지 않게 되고 그때 비어있음을 표시한 개수를 카운트하여 답을 리턴합니다.

 

---

[코드]

 

def solution(m, n, oldboard):
    answer = 0
    
    # 3 방향
    dx = [1, 0, 1]
    dy = [0, 1, 1]
    
    # 순회를 쉽게 하기위해 리스트형태로 바꿈
    board = []
    for i in range(m):
        temp = []
        for j in range(n):
            temp.append(oldboard[i][j])

        board.append(temp)

    # 변화가 없을 때까지 board를 계속 순회
    while True:
        isChange = False
        readyErase = []
        for i in range(m):
            for j in range(n):
                cur = board[i][j]
                tmp = [[i, j]]
                sameCnt = 1

                for idx in range(3):
                    nx = i + dx[idx]
                    ny = j + dy[idx]

                    if 0 <= nx < m and 0 <= ny < n:
                        if cur == board[nx][ny] and cur != -1:
                            tmp.append([nx, ny])
                            sameCnt += 1
                
                # 4블록이 완성되면 플레그 함수를 최신화 하고,
                # i, j의 위치를 기억
                if sameCnt == 4:
                    isChange = True
                    readyErase.append([i, j])
        
        # board의 한 번의 순회가 모두 끝나면 기억한 i, j를 기반으로 최신화
        for ready in readyErase:
            x, y = ready
            board[x][y] = -1
            board[x + 1][y] = -1
            board[x][y + 1] = -1
            board[x + 1][y + 1] = -1

        
        # board가 변하지 않으면 종료하고 종료하기전 사라진 블록의 개수를 계산
        if not isChange:
            # kprint(board)
            for i in range(m):
                for j in range(n):
                    if board[i][j] == -1:
                        answer += 1
            return answer
        
        # 변했다면 블록을 아래로 내리는 작업을 여기서 한다.
        for i in range(m - 1, 0, -1):
            for j in range(n):
                if board[i][j] == -1:
                    for idx in range(i, -1, -1):
                        if board[idx][j] != -1:
                            board[i][j] = board[idx][j]
                            board[idx][j] = -1
                            break

---

후기

 

시간이 걸렸지만 풀었습니다.

저보다 짧게 푼 사람도 있엇지만, 구현 문제이 만큼 원리는 같았습니다.

빼어나게 특별한 방법으로 푼 사람은 보이지 않았습니다.

저는 이정도 성과에 만족하고 다음에 이런 문제가 나왔을 때 더 빠르게 풀고 짧고 간결한

코드를 짤 수 있도록 계속 노력하고자 합니다.