카카오 코딩테스트 2019 블록 게임

종류 : 브루트포스

1. 사실 없앨 수 있는 블록의 모양은 다섯개 뿐이다

 - 검은 돌을 떨어트려서 꽉 찬 모양을 만들려면 동그라미 친 다섯 개 모양 중 하나여야 한다

2. 기준점을 (0, 0) 잡고 블록의 다른 부분을 상대좌표로 표현해준다 => types에 미리 저장

   - 채워야 할 부분은  empty에 상대좌표로 미리 저장해 놓는다

(x,y)를 기준점으로 잡았을 때 다른 부분의 상대좌표

types = [
	# 각 행은 모양의 인덱스
    [[1, 0], [1, 1], [1, 2]],
    [[1,0],[2,0],[2,-1]],
    [[1,0],[2,0],[2,1]],
    [[1,0],[1,-1],[1,-2]],
    [[1,0],[1, -1], [1, 1]]
]
empty=[
    [[0, 1], [0, 2]],
    [[0, -1], [1, -1]],
    [[0, 1], [1, 1]],
    [[0, -2], [0, -1]],
    [[0, -1], [0, 1]]
]

3. 어떤 모양인지 조사해서 blocks(큐)에 넣어준다

def which_type(board, x, y):
    global  visit
    num = board[x][y] # 이 칸에 쓰여진 숫자
    visit[num] = True
    h = len(board)
    w = len(board[0])
    for idx, type in enumerate(types):
        flag = True
        for i in range(3):
        	# 기준점에서 상대좌표를 더해주며 확인
            nx = x+type[i][0]
            ny = y+type[i][1]
            # 범위 체크 필수
            if nx<0 or nx>h-1 or ny<0 or ny>w-1:
                flag = False
                break
            # 해당 칸이 기준점과 같은 숫자여야 한다
            if board[nx][ny]!=num:
                flag = False
                break

        if flag:
            return idx
    return -1

 

4. 큐에 모양들을 넣고 없앨 수 있는지 판별해준다

  - while탈출 조건 : 해당 턴에 아무 것도 없애지 못했을 경우

 - 큐가 두 개인 이유 : 일단 blocks에서 다 pop한 후, 남아야 할 애들을 tmp에 저장하고 한 턴이 끝나면 다시 넣어준다

 flag = True
    while flag==True:
        flag = False
        tmp = deque()
        while len(blocks)!=0:
            block = blocks.popleft()
            if is_possible(board, block):
                flag = True
                board = delete(board, block)
                answer += 1
            else:
                tmp.append(block)
        while len(tmp)!=0:
            blocks.append(tmp.popleft())

5. is_possible() : 없앨 수 있는지 판별

 - 채워야 할 칸의 위로 다른 블록이 없어야 한다

 - 해당 위치의 열에서 위로 올라가며 다른 블록이 있는지 확인

def is_possible(board, block):
    x, y, type = block.x, block.y, block.type

    # 일단 첫 번째 빈 칸
    row = x+empty[type][0][0]
    col = y+empty[type][0][1]
    while row>=0:
        if board[row][col]!=0:
            return False
        row -= 1

    row = x+empty[type][1][0]
    col = y+empty[type][1][1]
    while row>=0:
        if board[row][col]!=0:
            return False
        row -= 1
    return True

6. delete() : board에서 블록 지우기

 

 

전체코드

from collections import deque

types = [
    [[1, 0], [1, 1], [1, 2]],
    [[1,0],[2,0],[2,-1]],
    [[1,0],[2,0],[2,1]],
    [[1,0],[1,-1],[1,-2]],
    [[1,0],[1, -1], [1, 1]]
]
empty=[
    [[0, 1], [0, 2]],
    [[0, -1], [1, -1]],
    [[0, 1], [1, 1]],
    [[0, -2], [0, -1]],
    [[0, -1], [0, 1]]
]
visit = [False for _ in range(200+1)]

class Block:
    def __init__(self, x, y, type):
        self.x = x
        self.y = y
        self.type = type

def which_type(board, x, y):
    global  visit
    num = board[x][y]
    visit[num] = True
    h = len(board)
    w = len(board[0])
    for idx, type in enumerate(types):
        flag = True
        for i in range(3):
            nx = x+type[i][0]
            ny = y+type[i][1]
            if nx<0 or nx>h-1 or ny<0 or ny>w-1:
                flag = False
                break
            if board[nx][ny]!=num:
                flag = False
                break

        if flag:
            return idx
    return -1

def is_possible(board, block):
    x, y, type = block.x, block.y, block.type

    # 일단 첫 번째 빈 칸
    row = x+empty[type][0][0]
    col = y+empty[type][0][1]
    while row>=0:
        if board[row][col]!=0:
            return False
        row -= 1

    row = x+empty[type][1][0]
    col = y+empty[type][1][1]
    while row>=0:
        if board[row][col]!=0:
            return False
        row -= 1
    return True

def delete(board, block):
    x, y, type = block.x, block.y, block.type
    board[x][y] = 0
    for i in range(3):
        nx = x+types[type][i][0]
        ny = y+types[type][i][1]
        board[nx][ny] = 0
    return board



def solution(board):
    answer = 0
    h = len(board)
    w = len(board[0])
    blocks = deque()
    for i in range(h):
        for j in range(w):
            num = board[i][j]
            if visit[num]==False and num!=0:
                type = which_type(board, i, j)
                if type!=-1:
                    blocks.append(Block(i, j, type))

    flag = True
    while flag==True:
        flag = False
        tmp = deque()
        while len(blocks)!=0:
            block = blocks.popleft()
            if is_possible(board, block):
                flag = True
                board = delete(board, block)
                answer += 1
            else:
                tmp.append(block)
        while len(tmp)!=0:
            blocks.append(tmp.popleft())
    return answer

board = [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]]
print(solution(board))