[프로그래머스] 3주차_퍼즐 조각 채우기

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

코딩테스트 연습 - 3주차

 

위클리 챌린지 3주차 문제이다. 갑자기 난이도가 올라갔다.

 

문제의 첫 번째 입출력 예로 설명을 하자면,

game_board =

[1, 1, 0, 0, 1, 0]
[0, 0, 1, 0, 1, 0]
[0, 1, 1, 0, 0, 1]
[1, 1, 0, 1, 1, 1]
[1, 0, 0, 0, 1, 0]
[0, 1, 1, 1, 0, 0]

이고 0으로 인접한 것들끼리 묶인 블록을 찾는다. (table 에서는 1)

 

예제의 도형은 6개로,

[0, 0, 1]  [0]  [0, 0]  [1, 0, 1]  [1, 0]  [0]
[1, 0, 1]  [0]  [0, 1]  [0, 0, 0]  [0, 0]
[1, 0, 0]

 

BFS 알고리즘을 통하여 위의 도형을 찾을 수 있다.

정확하게는 BFS 알고리즘을 이용하여 해당하는 도형의 [가장 왼쪽, 가장 위], [가장 오른쪽, 가장 밑] 좌표를 구한다.

l, t, r, b = min(left_index), min(top_index), max(right_index), max(bottom_index)

그리고 도형의 블록 개수, answer 에 더해질 값인 count 를 구하여 piece.append([l, t, r, b, count]) 를 한다. 

 

예로 piece 의 첫 번째 행은 [0, 2, 2, 4, 5] 이다. 이를 활용하여 2차원 배열인 game_board 를 slicing 하면, 도형이

[row[t:b+1] for row in game_board[l:r+1]] = [row[2:4+1] for row in game_board[0:2+1]] =

[0, 0, 1]
[1, 0, 1]
[1, 0, 0] 와 0의 개수가 5라는 것을 알 수 있다.

 

table 도 마찬가지로 도형을 구하여 piece2에 담아 piece와 piece를 비교하여 퍼즐 조각을 채울 수 있으면 count 를 answer 에 더해 answer 을 반환하면 된다.

 

piece2 에 있는 도형은 회전을 할 수 있으므로 rotate90 함수를 구현하여 4번의 비교를 한다. (0도, 90도, 180도, 270도)

piece2 에 있는 도형 또는 회전한 도형이 piece 에 있는 도형과 가로, 세로 길이와 count 가 일치하면 하나씩 비교하여 더했을 때 모든 값이 1이면 퍼즐 조각을 채울 수 있다고 판단할 수 있다. 퍼즐 조각을 채우면 사용된 도형이므로 piece2 에서 remove 해준다.

 

from collections import defaultdict, deque

def solution(game_board, table):
    answer = 0
    N = len(game_board)
    visit, visit2 = defaultdict(int), defaultdict(int)
    queue, queue2 = deque(), deque()
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    piece, piece2 = [], []
        
    for i in range(N):
        for j in range(N):
            if game_board[i][j] == 0:
                if visit[(i, j)] == 0:
                    l, t, r, b = i, j, i, j
                    visit[(i, j)] = 1
                    queue.append([i, j])
                    count = 1
                    
                    while queue:
                        x, y = queue.popleft()
                        
                        for d1, d2 in d:
                            if 0 <= x + d1 < N and 0 <= y + d2 < N and game_board[x + d1][y + d2] == 0 and visit[(x + d1, y + d2)] == 0:
                                queue.append([x + d1, y + d2])
                                l = min(l, x + d1)
                                t = min(t, y + d2)
                                r = max(r, x + d1)
                                b = max(b, y + d2)
                                visit[(x + d1, y + d2)] = 1
                                count += 1
                    
                    piece.append([l, t, r, b, count])
            
            if table[i][j] == 1:
                if visit2[(i, j)] == 0:
                    l, t, r, b = i, j, i, j
                    visit2[(i, j)] = 1
                    queue2.append([i, j])
                    count = 1
                    
                    while queue2:
                        x, y = queue2.popleft()
                        
                        for d1, d2 in d:
                            if 0 <= x + d1 < N and 0 <= y + d2 < N and table[x + d1][y + d2] == 1 and visit2[(x + d1, y + d2)] == 0:
                                queue2.append([x + d1, y + d2])
                                l = min(l, x + d1)
                                t = min(t, y + d2)
                                r = max(r, x + d1)
                                b = max(b, y + d2)
                                visit2[(x + d1, y + d2)] = 1
                                count += 1
                    
                    piece2.append([l, t, r, b, count])
    
    for l, t, r, b, count in piece:
        for l2, t2, r2, b2, count2 in piece2:
            A = [row[t:b+1] for row in game_board[l:r+1]]
            B = [row[t2:b2+1] for row in table[l2:r2+1]]
            
            if count == count2:
                c = 0
                T = False
                
                while c < 4 and not T:
                    c += 1
                    n = len(A)
                    m = len(A[0])
                    
                    if n == len(B) and m == len(B[0]):
                        for i in range(n):
                            for j in range(m):
                                if A[i][j] + B[i][j] != 1: break

                                if i == n - 1 and j == m - 1:
                                    T = True
                                    break

                            if A[i][j] + B[i][j] != 1 or T: break
                    
                    B = rotate90(B)
            
                if T:
                    answer += count
                    piece2.remove([l2, t2, r2, b2, count2])
                    break
        
    return answer
        
def rotate90(key):
    n = len(key)
    m = len(key[0])
    
    key_ = [[0] * n for i in range(m)]
    
    for i in range(n):
        for j in range(m):
            key_[j][n-i-1] = key[i][j]
    
    return key_
    
    print(solution([[1, 1, 0, 0, 1, 0], [0, 0, 1, 0, 1, 0], [0, 1, 1, 0, 0, 1], [1, 1, 0, 1, 1, 1], [1, 0, 0, 0, 1, 0], [0, 1, 1, 1, 0, 0]], [[1, 0, 0, 1, 1, 0], [1, 0, 1, 0, 1, 0], [0, 1, 1, 0, 1, 1], [0, 0, 1, 0, 0, 0], [1, 1, 0, 1, 1, 0], [0, 1, 0, 0, 0, 0]])) # 14