LV2 [KAKAO] [1차] 프렌즈4블록

---

문제

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

프로그래머스

 

풀이

 

간단한 시뮬레이션 문제이다. 4개의 블록을 없애고, 밑으로 옮겨주는 행동을 반복적으로 하다가 없어지는 블록이 더이상 존재하지 않을 경우 답을 return 해주면 된다.

 

4개의 블록을 없애는 로직은

1. 2차원 배열로 접근한다음 현재위치값과, 아래, 오른아래대각, 오른 좌표들이 모두 같은지 확인한다.
   (입력으로 들어오는 값은 문자열이라 list로 바꾸어주는 작업을 진행했다.)
2. 같다면 각 좌표들을 저장한다 (없어지는 블록이 겹칠경우 중복이 일어날 수 있으니 set자료구조를 활용한다.)
3. set에 저장되어 있는 개수가 없어지는 블록의 개수니 답에 더해준다.
4. set에 저장되어 있는 좌표들을 참고하여 값을 비워준다.

이 과정에서 set의 길이가 0이면 없어지는 블록이 없으니 답을 return 해주면 된다.

 

그게 아니라면 블록을 내려준다.

 

블록을 내려주는 방식이야 구현하기 나름인데, 나는 가장 아래 요소 - 1 부터 내려야하는지 체크했다.

가장 아래로 내려야하기에 가장 아래요소부터 0이라면(비어있다면) 즉각적으로 내려주는 방식으로 구현했고, 내가 내릴려 했던 값까지 인덱스가 올라오면 내릴수 없다는 것이기에 넘어갔다.

 

코드

def getRemoveList(x, y, r, c, ch, board):
    
    positions = [(0, 1), (1, 1), (1, 0)]
    temp = [(x, y)]

    for p in positions:
        nx = x + p[0]
        ny = y + p[1]
        
        if 0 <= nx < r and 0 <= ny < c and board[nx][ny] == ch:
            temp.append((nx, ny))
    
    if len(temp) == 4: return temp
    return False
    
    
def readjustBoard(r, c, board):
    for i in range(c):
        for j in range(r-2, -1, -1):
            
            if board[j][i] == 0: continue
            k = r-1
            while True:
                if k==j : break
                if board[k][i] == 0: break
                k-=1
            
            if k!=j:
                board[k][i] = board[j][i]
                board[j][i] = 0

    return board

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

    while True:
        ansList = set()
        for i in range(r):
            for j in range(c):
                if board[i][j] != 0:
                    idxList = getRemoveList(i, j, r, c, board[i][j], board)
                    if idxList:
                        for v in idxList: ansList.add(v)

        # 만약 ansList가 비어있다면, 반복문을 탈출하고 종료하면 된다.
        if len(ansList) == 0 :
            return answer

        answer += len(ansList)
        
        # 그 외에는 0으로 바꿈
        for v in ansList:
            board[v[0]][v[1]] = 0

        # 모든 칸을 아래로 내려준다.
        board = readjustBoard(r, c, board)

 

후기

 

처음에 블록을 부술때 좌상단 기준, 우상단 기준, 좌하단 기준, 우하단 기준에서 모두 검사했다.

그런데 생각해보니 좌상단에서 우하단으로 모두 탐색하기에 좌상단 기준으로만 블록을 검사해도 답을 낼 수 있었다.