[Python] 프렌즈4블록

def delete(temp, column, count) :
    for change in temp :
        if column[change] != 0 :
            column[change] = 0
            count += 1
    return column, count


def match(m, board, column_1, count):
    new_board = []
    temp = []
    
    while board :
        column_2 = list(board.pop())
        temp_2 = []
        for block in range(m-1):
            if column_1[block] == column_1[block+1] == column_2[block] == column_2[block+1] :
                temp.append(block)
                temp.append(block+1)
                temp_2.append(block)
                temp_2.append(block+1)

        column_1, count = delete(temp, column_1, count)
        temp = temp_2
            
        new_board.append(column_1)
        column_1 = column_2
        
    column_2, count = delete(temp, column_2, count)
    new_board.append(column_2)

    return new_board, count


def solution(m, n, board):
    
    board = list(zip(*board))
    count = 0
    
    while True :
        column_1 = list(board.pop())
        count_2 = count
        board, count = match(m, board, column_1, count)
        
        if count_2 == count : 
            break
        for i in range(n) :
            board[i].sort(key=lambda x : x == int(), reverse=True)
        
    return count

---

풀이

 

1) 메인 함수

def solution(m, n, board):
    
    board = list(zip(*board))
    count = 0
    
    while True :
        column_1 = list(board.pop())
        count_2 = count
        board, count = match(m, board, column_1, count)
        
        if count_2 == count : 
            break
        for i in range(n) :
            board[i].sort(key=lambda x : x == int(), reverse=True)
        
    return count

 

1. board는 행별로 입력되어있는데, 블럭이 사라질때 아래로 떨어지므로 board를 뒤집어 주었다.(열 별로 구성됨)

2. While문 : 사라진 블럭이 없어질때까지 반복

1. pop(0)은 O(n)의 시간이 걸린다. 따라서 오른쪽부터 시작해도 상관 없으니 pop()을 이용해 왼쪽으로 이동하며 두개의 열 차례로 비교해주었다. (위의 그림 참고)
2. match 함수를 만들어 같은 블럭들이 있다면 count한 뒤, 0으로 바꾸어준 새로운 board를 받아온다.
3. match 함수를 진행했음에도 count의 값이 변화가 없다면 while문을 중단한다. (count_2에 이전 count의 값을 저장시켜줌)
4. 반복문을 통해 남아있는 블럭들을 아래로 이동시켜준다
   • 사라진 블럭을 0으로 바꾸어주었기 때문에 sort함수를 이용하여 int를 앞으로 당기는 방식을 이용했다.

3. 누적된 count를 반환한다.

 

 

2) 네개의 같은 블럭 찾고 새로운 board 생성하는 함수

def match(m, board, column_1, count):
    new_board = []
    temp = []
    
    while board :
        column_2 = list(board.pop())
        temp_2 = []
        for block in range(m-1):
            if column_1[block] == column_1[block+1] == column_2[block] == column_2[block+1] :
                temp.append(block)
                temp.append(block+1)
                temp_2.append(block)
                temp_2.append(block+1)

        column_1, count = delete(temp, column_1, count)
        temp = temp_2
            
        new_board.append(column_1)
        column_1 = column_2
        
    column_2, count = delete(temp, column_2, count)
    new_board.append(column_2)

    return new_board, count

1. 새로운 board를 받을 리스트와, 없어질 블록들의 인덱스를 받는 리스트를 생성해준다.

2. while문 : 예전 board가 빌 때까지 반복.

    column 두개(1번 2번이라고 가정)를 받아와 비교한 후, 1번 column에서 사라져야하는 블록이 있다면 블록을 0으로 변환한 후, 새로운 board에 넣어준다. 2번 column은 그 다음 column과 비교해야하므로 column_1 변수로 넣어준다. 이러한 방식을 반복한다.

1. column_1과 column_2는 나중에 사라진 블록의 값을 변환하기 위해 리스트로 변환해주었다.
2. for문을 통해 column_1열을 돌면서 붙어있는 네 블럭이 같다면 각 temp에 해당 블럭 인덱스를 저장해준다. 
   • 중복이 있을 수 있으므로 바로 삭제해주지 않고 인덱스를 저장한다. ex) "AAAT", "AAAB"
   • temp_2에도 저장하는 이유는 column_2는 column_1과 비교했을 때, 0으로 바뀌어야할 블록이 있고 다음 열(column_2의 다음)과 비교한 후, 변환해주어야 하기 때문이다.
3. 다 돈다면, delete 함수를 통해 삭제될 블럭들을 0으로 바꾸어준다.
4. column_1을 새 보드에 추가시킨뒤, column_2를 column_1로 대체시켜준다.

3. 마지막 열은 while문에서 블럭이 변환되고 새보드에 추가되지 않으므로 따로 시켜준다.

4. 새 보드와 누적된 count를 블럭을 반환해준다.

 

 

3) 블럭 삭제 및 count하는 함수

def delete(temp, column, count) :
    for change in temp :
        if column[change] != 0 :
            column[change] = 0
            count += 1
    return column, count

1. 사라질 블럭의 인덱스가 담긴 temp 리스트를 받아와 해당 열의 블록들을 0으로 변환시켜준다.

2. 해당하는 값(column[change])이 0이 아닐때만(블럭이 있을때만) 0으로 변환시켜주고 count해준다.

• if문을 쓴 이유는 사라지는 블럭의 중복인 경우가 있기때문에 count의 중복을 막기 위함이다.

3. 해당 열과 누적된 count를 반환한다.