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

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

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

 

문제 이해

---

2D array 블록에서 정사각형의 2X2 블록이 모두 동일하다면, 터지고 아래로 내려오는데 이 때 터진 총 갯수

혹시나 별도의 풀이 방법이 들어갈까 생각을 하여보았지만, 별도로 생각 나는게 없어서 블록 내리기 식으로 구현하였습니다.

 

알고리즘

---

 

1. Maps 라는 2D array를 설정 ( 문자열보다 List index 접근 위함 )

2. 각 블록의 경우 기준을 잡은 블록의 우측 / 아래 / 대각선 우측 아래가 동일하다면 터진다라고 접근하였습니다.

3. 바로 블록을 터뜨리기에는 동시에 터지는 경우가 발생하여, 해당 데이터를 모아둡니다. ( 겹치는 부분이 생김으로 Set )

4. 터지는 블록들은 임의의 값으로 설정 및 answer 값 추가

5. 블록들을 아래로 내리기

6. 터진 블록이 있는 경우 2~5 반복

 

코드

---

def solution(m, n, board):
    answer = 0
    maps = [['0']*n for _ in range(m)]
    dx , dy = [0,1,1] , [1,0,1]

    #init
    for i in range(m) :
        for j,data in enumerate(board[i]) :
            maps[i][j] = data
            
    while True :  
        delete_arr = set()
        #find_delete_xy 
        for x in range(m-1) :
            for y in range(n-1) :
                if maps[x][y] == '-':
                    continue
                check = True
                for t in range(3) :
                    nx,ny= x+dx[t],y+dy[t]
                    if maps[nx][ny] != maps[x][y] :
                        check = False
                        break

                if check :
                    delete_arr.add((x,y))
                    for t in range(3) :
                        nx,ny= x+dx[t],y+dy[t]
                        delete_arr.add((nx,ny))
        
        if not delete_arr :
            break
        #explose block
        for arr in delete_arr :
            maps[arr[0]][arr[1]]='0'
        answer += len(delete_arr)
        
        #down block
        for y in range(n) :
            for x in range(m-1,-1,-1) :
                while maps[x][y] == '0' :
                    for t in range(x,0,-1) :
                        maps[t][y] = maps[t-1][y]
                    maps[0][y] = '-'
                    
    return answer