[프로그래머스] 위클리챌린지 3주차 #python

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

코딩테스트 연습 - 3주차_퍼즐 조각 채우기

1. bfs(start, end, table, visited, target)

해당 블럭모양의 위치를 찾습니다.  start와 end는 블럭의 시작위치를 의미하고 table은 bfs를 할 테이블

visited는 해당 블럭의 방문여부, target은 현재배열의 값이 1인지 0인지 여부를 구할 때 필요합니다.

bfs조건에 맞는 위치정보는 route에 저장되어 반환됩니다. 단 이때, 위치는 (0, 0)을 기반으로 좌표이동 해주어야 합니다.

 

2. rotate_block(block_info, n):

block_info에 있는 위치정보를 오른쪽방향으로 90도 회전해준 후에 반환합니다.

 

3. find_block(block_info, set_of_blocks, n):

block_info를 총 4번 회전하며 set_of_blocks 에 같은 값이 있는지 비교합니다.

같은 값이 있으면 블럭의 길이를 반환해주고 그렇지 않으면 0을 반환합니다.

단, 이때 block_info를 90도 회전한 후에, (0, 0)좌표로 이동한 정보를 new_info에 저장하여 줍니다.

block_info에 있는 정보 자체를 (0, 0)좌표로 이동한 후에 그 정보를 가지고 계속 회전시켜주면,

좌표값이 set_of_blocks에 저장해준 값과 맞지 않을 수 있습니다.

 

4. solution(game_board, table):

number_of_blocks: table에 있는 블럭들의 위치를 블럭의 길이 별로 저장하여 줍니다. 굳이 구현해 줄 필요는 없으나, 저는 시간을 실행시간을 줄이기 위해 분류해두었습니다.  

먼저 table에서 블럭들의 위치들을 bfs하여 set_of_blocks 저장하고 game_board에서 빈공간을 찾아 그 길이에 해당하는 값들을 set_of_blocks 찾아서 find_block함수에 사용해주었습니다.

 

 

from collections import defaultdict
from collections import deque

def bfs(start, end, table, visited, target):
    n = len(table)
    stack = deque([(start, end)])
    route = set([(0, 0)])
    
    while stack:
        x, y = stack.popleft()
        for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n:
                if table[nx][ny] == target and visited[nx][ny] == 0:
                    visited[nx][ny] = 1
                    stack.append((nx,ny))
                    route.add((nx-start, ny-end)) # 시작점 (0, 0)으로 이동
    return route        

def rotate_block(block_info, n):
    new_info = set()
    for x, y in block_info:
        new_info.add((y, n-x-1)) # rotate
        
    return new_info

    
def find_block(block_info, set_of_blocks, n):
    for _ in range(4):
        dx, dy = min(block_info)
        new_info = set()
        for x, y in block_info:
            new_info.add((x-dx, y-dy)) # 시작점 (0, 0)으로 이동
        if new_info in set_of_blocks:
            set_of_blocks.remove(new_info) # 사용된 블럭지우기
            return len(new_info)
        
        block_info = rotate_block(block_info, n)
        
    return 0
    
    
def solution(game_board, table):
    answer = 0
    num_of_blocks = defaultdict(list)
    n = len(table)
    
    # 블럭의 개수별로 블럭의 위치 저장
    visited = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if table[i][j] == 1 and visited[i][j] == 0:
                visited[i][j] = 1
                block_info = bfs(i, j, table, visited, 1)            
                num_of_blocks[len(block_info)].append(block_info)
    
    # 빈공간찾기
    visited = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if game_board[i][j] == 0 and visited[i][j] == 0:
                visited[i][j] = 1
                empty_block = bfs(i, j, game_board, visited, 0)
                #print(empty_block)
                if len(empty_block) in num_of_blocks:
                    answer += find_block(empty_block, num_of_blocks[len(empty_block)], n)
                
    return answer

이 문제는 상당히 복잡해 보이지만, 생각하고자하는 실행방법을 순서대로 코딩한다면 크게 어려움없이 풀 수 있는 문제였습니다.

어떻게 풀지 아이디어를 생각하는것보다 코딩의길이가 길어지면서 도중에 변수명이 꼬인걸 해결하는데 더 시간이 걸렸습니다.

개인적으로 중첩함수를 선호하지 않는 편이라 따로 분리해주다보니 이렇게 됐는데, 너무 많은 함수 값은 지양하도록 해야할 것 같습니다.