[카카오] 2019 카카오 블라인드 #7 블록 게임 (Python)

 

https://school.programmers.co.kr/learn/courses/30/lessons/42894?language=python3

프로그래머스

 

빡센 구현문제. 그래도 해설 안 보고 풀었다...!

 

풀이

 

블록이 사라지긴 위해선 2*3 혹은 3*2 직사각형 크기가 되어야 한다.

발그림 ㅈㅅ

이는 해당 블록의 빈 공간에 검은 블록이 채워져 있으면 블록이 사라짐을 의미 한다. 

구현 아이디어

1. 블록 삭제 사이클을 돌리기전 사전 작업을 수행한다. 이는 맨 위 블록이 닿기 전 까지 모든 수직 배열에 검은 블록을 채우는 것이다. 검은 블록은 숫자를 -1(board[x][y] = -1)로 설정해 구현하였다.

 

2. 모든 블록의 "직사각형 모양 시작과 끝점좌표" 를 구한뒤 배열로 저장한다. (minx,miny,maxx,maxy) 이 배열을 통해 향후 블록의 삭제 여부를 결정한다.

 

3. 위에서 부터 사이클을 돌린다. 블록을 발견하면 2에서 구한 배열에서 해당 블록의 시작과 끝 범위를 구한다. 2 * 3 혹은 3*2 직사각형 범위 에서 검은 블록의 갯수가 2개인지를 확인 한다.

 

4. 맞으면 블록 삭제

 

5. 블록 삭제후 수직 방향으로 검은 블록을 채운다.

 

이후 반복!

 

해맷던 부분

6 번 로직에서 문제가 발생해 꽤 애먹었다... 처음에는 단순히 삭제한 블록의 수직방향으로 검은 블록을 생성하였다. 하지만 이는 오류가 있었는데, 삭제한 블록 위에 다른 블록의 존재 여부를 생각 하지 않았던 것이였다. 물론 검은 블록은 위에 다른 블록이 없어야 생성되는 것이 맞았지만, 검은 블록이 아닌 다른 블록 위에는 당연히 다른 블록이 존재 했던것...

ex) (아랫 블록 왼쪽 위에 윗 블록이 존재 한다. 검은 블록이 생성 되지 못한다. )

 __

    l

    

    l__

 

그래서 6의 로직을 삭제한 블록의 인덱스에서 시작이 아닌, 0번째 인덱스에서 시작하는 것으로 바꾸었다.

( for _j in range(삭제 블록 x: n) -> for _j in range(n) )

 

이 부분 때문에 자꾸 오류가 발생해 30분 이상은 해멧던거 같다.. ㅜㅜㅜ

 

 

소스 코드

n = 0

dx = [0,1,0,-1]
dy = [1,0,-1,0]
# 블록의 시작점과 끝점을 구한다.
def getBlock(x,y,color,board,visited):
    global n
    q = [(x,y)]
    res = [(x,y)]
    while q:
        x,y = q.pop()
        
        for i in range(4):
            nx = x +dx[i]
            ny = y +dy[i]
            if -1 < nx < n and -1 < ny < n and board[nx][ny] == color and not(visited[nx][ny]):                
                visited[nx][ny] = True
                q.append((nx,ny))
                res.append((nx,ny))
                
    minx = miny = 1000000001
    maxx = maxy = -1
    for block in res:
        x,y = block
        minx = min(minx,x)
        miny = min(miny,y)
        maxx = max(maxx,x)
        maxy = max(maxy,y)
        
    return [(minx,miny), (maxx,maxy)]

def go(board,blocks):
    global n
    deleted = 0
    
    for i in range(n):
        for j in range(n):
            if board[i][j] >0:
                color = board[i][j]
                # 검사
                begin, end = blocks[color]
                
                cnt = 0
                for _i in range(begin[0], end[0] +1):
                    for _j in range(begin[1], end[1] +1):
                        if board[_i][_j] == -1:
                            cnt +=1            
                
                # 검은 블록 2개 이상                            
                # 밑에 다 검은 블록으로
                if cnt == 2:
                    deleted +=1
                    for _i in range(begin[1], end[1] +1):
                        # 위에 다른 블록이 걸릴수가 있다.. x는 0부터 꼭 확인!
                        # ㄱ
                        #  ㄴ                       
                        for _j in range(n):
                            if board[_j][_i] <=0 or board[_j][_i] == color:
                                board[_j][_i] = -1
                            else:
                                break
    return deleted

def solution(board):
    global n
    answer = 0
    blocks = [[] for _ in range(201)]
    n = len(board)
    visited = [[False for _ in range(n)] for _ in range(n)]
    # 모든 블록의 시작,끝점을 구한다.    
    for i in range(n):
        for j in range(n):
            if board[i][j] >0 and not(visited[i][j]):
                blocks[board[i][j]] = getBlock(i,j,board[i][j],board,visited)
            
    # 검은 블록 채우기 
    for i in range(n):
        for j in range(n):
            if board[j][i] == 0:
                board[j][i] = -1
            else:
                break
    # 사이클 시작             
    answer = go(board,blocks)
        
    return answer