[위클리 챌린지] 3주차

https://programmers.co.kr/learn/courses/30/lessons/84021#

코딩테스트 연습 - 3주차

 

간소화랑 효율성 고려안하고 짜서 그런지 코드가 좀 난잡하다.

 

- 풀이

 

1. table에 대해 각각의 블럭에 대해 아래와 같은 배열을 만든다.

0	0	0	0	0	0
0	0	1	0	0	0
0	1	1	0	0	0
0	0	1	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0

 

2. game_board에 대해서도 위와 같이 배열을 만든다.

3. 2번에서 만든 빈칸배열(board)에 대해 맞는 블럭을 찾는다.

4. 블럭과 빈칸의 크기가 같고 check()함수가 True라면, answer에 합산, 그리고 한 블럭이 두개이상의 빈칸에 들어가는 것을 막기위해 삭제

5. check함수

  - block을 회전시키면서 맞는지 비교

  - 블럭과 빈칸의 위치를 list1, list2에 좌표형태로 추가

EX) 위와 같은 'ㄱ'자 블럭과 빈칸을 나타내는 두 배열에 대해

list1 = [[0,0], [0,1], [1,0]]

list2 = [[1,1], [1,2], [2,1]] 

이라 할 때, list1 - list2 = [[-1,-1], [-1,-1], [-1,-1]]

list1[:, 0]값들이 다 같고, list2[:, 1]값도 다 같으면 같은 모양이라고 할 수 있다.

* unique() : 유일한 값들을 반환한다.

 

 

import numpy as np
def solution(game_board, table):
    answer = 0  

### table블럭 구하기 ###
    blocks = []
    for i in range(len(table)):
        for j in range(len(table[i])):
            if table[i][j]: #블럭이 있으면
                table[i][j] = 0
                queue = [[i, j]]
                block = np.zeros((len(table), len(table)))
                block[i][j] = 1
                while queue:
                    x, y = queue[0][0], queue[0][1]
                    del queue[0] 
                    if y+1 < len(table[x]) and table[x][y+1]==1: #좌
                        queue.append([x, y+1])
                        table[x][y+1] = 0
                        block[x][y+1] = 1
                    if y > 0 and table[x][y-1]==1: #우
                        queue.append([x, y-1])
                        table[x][y-1] = 0
                        block[x][y-1] = 1
                    if x > 0 and table[x-1][y]==1: #상
                        queue.append([x-1, y])
                        table[x-1][y] = 0
                        block[x-1][y] = 1
                    if x+1 < len(table) and table[x+1][y]==1: #하
                        queue.append([x+1, y])
                        table[x+1][y] = 0
                        block[x+1][y] = 1
                blocks.append(np.array(block))

### game_board블럭 구하기 ###                
    cnt = 0 #debug
    for i in range(len(game_board)):
        for j in range(len(game_board[i])):
            if not game_board[i][j]: #빈칸이면
                game_board[i][j] = 1
                queue = [[i, j]]
                block = np.zeros((len(game_board), len(game_board)))
                block[i][j] = 1
                while queue:
                    x, y = queue[0][0], queue[0][1]
                    del queue[0] 
                    if y+1 < len(game_board[x]) and game_board[x][y+1]==0: #좌
                        queue.append([x, y+1])
                        game_board[x][y+1] = 1
                        block[x][y+1] = 1
                    if y > 0 and game_board[x][y-1]==0: #우
                        queue.append([x, y-1])
                        game_board[x][y-1] = 1
                        block[x][y-1] = 1
                    if x > 0 and game_board[x-1][y]==0: #상
                        queue.append([x-1, y])
                        game_board[x-1][y] = 1
                        block[x-1][y] = 1
                    if x+1 < len(game_board) and game_board[x+1][y]==0: #하
                        queue.append([x+1, y])
                        game_board[x+1][y] = 1
                        block[x+1][y] = 1
                cnt += 1    
### 빈칸에 맞는 블럭인지 체크 후 answer에 추가 ###
                for k in range(len(blocks)):
                    if blocks[k].sum()==np.array(block).sum() and check(blocks[k], block):  #테이블, 보드
                        answer += blocks[k].sum()
                        block = []
                        del blocks[k]
                        break
    return answer

### 블럭을 돌려가며, 칸에 맞는지 체크 ###
def check(block, board):
    for k in range(4):  #rotate 90 180 270 360
        block = np.rot90(block)
        list1, list2 = [], []
        for i in range(len(block)):
            for j in range(len(block[i])):
                if block[i][j] == 1:
                    list1.append([i, j])
                if board[i][j] == 1:
                    list2.append([i, j])
        temp = np.array(list1) - list2  #np.array는 리스트간의 연산이 가능
        if len(np.unique(temp[:,0]))==1 and len(np.unique(temp[:,1]))==1:
            print(temp)
            return True
    return False