[파이썬] 프로그래머스 - [1차] 프렌즈4블록

문제 설명

 

 

처음 생각한 풀이

1. 게임판의 값이 '*'이 아니라면, 해당 좌표, 좌, 하, 대각(왼아) 좌표를 탐색하고 값이 모두 같다면 그 좌표들을 리스트에 담는다.

2. 사라질 좌표들의 중복을 없애고, 그 좌표의 값을 '*'로 대체한다.

3. '*' 위의 문자들을 밑으로 내리고, 사라질 좌표들이 하나도 없을 때까지 1부터 반복한다.

 

문제점

풀이 방식을 떠올리는 건 쉽지만, 좌표의 값을 '*'로 대체하고, '*' 위의 문자를 밑으로 내리는 걸 구현하는게 어려웠습니다.

for i in range(n):
    for j in range(m-1):
    	if board_list[j][i] != '*' and board_list[j+1][i] == '*':
     	    board_list[j][i], board_list[j+1][i] = board_list[j+1][i], board_list[j][i]

1) 처음엔 단순히 현재 좌표의 값이 '*'이 아니고, 바로 밑 좌표의 값이 '*'이면 값을 바꾸라는 식으로 구현하였습니다.

2) 그러나 이럴경우엔 

T                   T

C                   *

*        ->        *

*                    C

A                   A

밑에있는 C만 내려가고, T는 밑 좌표가 '*'이 아니었기 때문에 그대로 있게 됩니다.

for i in range(n):
    for j in range(m-1, 0, -1):
        if board_list[j][i] == '*' and board_list[j-1][i] != '*':
            board_list[j][i], board_list[j-1][i] = board_list[j-1][i], board_list[j][i]

3) 2번의 경우를 커버하기 위해서 밑에서 부터 for문을 도는 식으로 변경하였습니다.

4) 그러나 이 경우에도

T                   *

C                   T

*        ->        C

*                    *

A                   A

한 칸씩 밖에 안내려가게 됩니다. 그렇기 때문에 여기에 while문을 추가하여 내리는 것을 해결 하였습니다.

 

코드

# 붙어있는 4개의 블록이 있는지 확인 후, 있다면 좌표를 가져옴
def search(bi, bj, board_list, m, n):
    di = [1, 1, 0]  # 하, 대각(오아), 우 탐색시 사용
    dj = [0, 1, 1]  # 하, 대각(오아), 우 탐색시 사용 
    is_valid = True # 유효하지 않을 때 거르는 bool 변수
    coor = []
    for k in range(3):
        ki = bi + di[k]
        kj = bj + dj[k]
        if ki >= m or kj >= n or board_list[ki][kj] != board_list[bi][bj]:
            is_valid = False
            break
    if is_valid:
        coor.append([bi, bj])
        for k in range(3):
            ki = bi + di[k]
            kj = bj + dj[k]
            coor.append([ki, kj])
    
    return coor
    
def solution(m, n, board):
    answer = 0          # 최종 '*'의 개수
    board_list = []     # 문자열 자체는 인덱스로 해당값을 수정할 수 없기 때문에 list로 변경
    vanish_coor = []    # 사라질 좌표
    
    # 문자열을 담은 list를 2차원 list로 수정
    for i in range(m):
        board_list.append(list(board[i]))

    while True:
        # 4개의 블록 탐색하기
        for i in range(m):
            for j in range(n):
                if board_list[i][j] != '*':
                    vanish_coor += search(i, j, board_list, m, n)
        
        # 사라질 블록이 없다면 종료
        if len(vanish_coor) == 0:
            break
                
        # 사라질 블록에 '*' 대입
        for i in range(len(vanish_coor)):
            board_list[vanish_coor[i][0]][vanish_coor[i][1]] = '*'
    
        # '*' 위의 문자들 다시 밑으로 내려오게 수정
        for i in range(n):
            for j in range(m-1, 0, -1):
                if board_list[j][i] == '*' and board_list[j-1][i] != '*':
                    index = j
                    while index <= m - 1 and board_list[index][i] == '*':
                        board_list[index][i], board_list[index-1][i] = board_list[index-1][i], board_list[index][i]
                        index += 1
        
        # 사라질 블록 좌표 클리어
        vanish_coor.clear()
        
    # '*'의 개수 세기
    for i in range(m):
        for j in range(n):
            if board_list[i][j] == '*':
                answer += 1
            
    return answer