[ 프로그래머스 ] 퍼즐 조각 채우기

사실 문제 푸는데 집중을 못 했다.. 아침에 뉴스를 보고 왔더니 계속 생각나면서 여러 생각이 났다.

계획한 45분 내에 푸는 것 실패.

시간 지났어도 더 풀어보려고 했는데 dfs부분 순간 헷갈리면서 더 진행할 마음이 안 나서 그냥 풀이 보고 공부하기로 했다.

 

from collections import deque
def dfs(blocks, depth):
    if depth == len(blocks):
        return
        
    # 이 아래 부분을 구현하다가 그냥 포기했다. 
    for b in blocks:
        dfs(blocks, depth+1)
    
        
def solution(game_board, table):
    answer = -1
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 블럭 찾아서 모양대로 배열에 넣기
    blocks = []
    block_visit = [[False]*len(table[0]) for _ in range(len(table))]
    for i in range(len(table)):
        for j in range(len(table[0])):
            if table[i][j] == 1 and not block_visit[i][j]:
                block = []
                q = deque([(i, j)])
                block.append((i, j))
                while q:
                    x, y = q.popleft()
                    block_visit[i][j] = True
                    for k in range(4):
                        nx, ny = x+dx[k], y+dy[k]
                        if 0 <= nx < len(table) and 0 <= ny < len(table[0]) and table[nx][ny] == 1 and not block_visit[nx][ny]:
                            q.append((nx, ny))
                            block.append((nx, ny))
                            block_visit[nx][ny] = True
                blocks.append(block)
    
    # 각 블럭 넣어가며(넣을 때 회전해가며) 체크(dfs)
    dfs(blocks, 0)
    
    return answer

 

 

일단 문제 보고 세운 순서는 이랬다.

1. table을 bfs로 훑으며 블럭들 찾아서 따로 저장하기

2. 각 블럭 dfs로 조건에 맞게 가능한만큼 (돌려가며)넣다 빼면서 최대 개수 갱신해나가기

 

1번까지 완료하고 2번을 풀이 보고 하기로 한다. 

1번도 사실 저게 아쉬운게.. 저렇게 해당하는 좌표 묶음으로 만드는게 아니라, 0으로 채워서 사각형 모양으로 만들고 싶었다. 끈기나 구현이나 여러모로 스스로에게 실망스럽고 아쉬움이 남는 문제다. 

 

 

벨로그 Kerri.log , Kerri님 풀이 

내가 풀이하고 싶었던 방향으로 하나하나 풀 구현하셔서 오..했다. 

그런데 보고 공부하면서도 시간이 오래 걸릴 것 같은 시간 낭비 포인트들이 조금 보였는데, 역시나 시간초과가 나더라. 

for문 중첩 등.. 

 

아이공 님 풀이

통과도 했고 시간 소모도 없었다.

아예 맵을 기준으로 체크해버린다. 맵에서 빈 공간을 블럭으로써 좌표값으로 배열에 저장해두고, 

블럭판을 돌려가면서 해당 블럭 좌표가 나오면, 윗 줄에서 언급한 배열에 있는 지 여부로 체크해버린다. 

곱씹어볼만하다.. 내일도 봐야징.

 

.

.

 

생각해보면 이런 식의 도형 끼워넣기 문제(그니까 퍼즐..)는 되게 여러 번 풀었던 것 같은데 아직도 구현을 완벽하게 못 한다는게 .. 헛공부한 느낌이 들어서 헛헛하다.. 학습은 반복이라고.. 그냥 반복의 과정이겠거니.. 라고 좋게좋게 생각해야 꾸준히 공부를 이어나가려나..? 한 달 내로 기본적인 코테는 패스하는 수준으로 역량 올리겠다는 확고한 마음이 생겨서 좀 자기채찍질이 강해진다. 좋은 것 같다. 그간은 스스로를 너무 사랑하고 아껴왔다.. 안 좋은 방향으로 ^^