[파이썬] 프로그래머스 - 위클리 챌린지 3주차

• 퍼즐 조각 채우기

문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

다음은 퍼즐 조각을 채우는 예시입니다.

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.

이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 3 ≤ game_board의 행 길이 ≤ 50
• game_board의 각 열 길이 = game_board의 행 길이
  • 즉, 게임 보드는 정사각 격자 모양입니다.
  • game_board의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
  • 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• table의 행 길이 = game_board의 행 길이
• table의 각 열 길이 = table의 행 길이
  • 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
  • table의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
  • 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• game_board에는 반드시 하나 이상의 빈칸이 있습니다.
• table에는 반드시 하나 이상의 블록이 놓여 있습니다.

---

입출력 예

game_boardtableresult

[[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
[[0,0,0],[1,1,0],[1,1,1]]	[[1,1,1],[1,0,0],[0,0,0]]	0

---

입출력 예 설명

입출력 예 #1

입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

입출력 예 #2

블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

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

코딩테스트 연습 - 3주차

 

---

import collections
#아래,오른쪽,위,왼쪽
x_move = [1,0,-1,0]
y_move = [0,1,0,-1]
table_num_dict = collections.defaultdict(list)
board_num_dict = collections.defaultdict(list)

def bfs(table, table_num, init, x, y):
    q = collections.deque()
    q.append([x,y])
    table[x][y] = table_num
    tmp_path = [x, y]
    visited = [[0 for y in range(len(table))] for x in range(len(table))]
    if init == False:
        visited[x][y] = 1
    
    while q:
        now_x, now_y = q.popleft()
        
        for i in range(len(x_move)):
            next_x, next_y = now_x+x_move[i], now_y+y_move[i]
            if 0 <= next_x < len(table) and 0 <= next_y < len(table):
                if init == True and table[next_x][next_y] == 1:
                    q.append([next_x, next_y])
                    table[next_x][next_y] = table_num
                    tmp_path.extend([next_x, next_y])
                if init == False and visited[next_x][next_y] != 1 and table[next_x][next_y] == table_num:
                    q.append([next_x, next_y])
                    visited[next_x][next_y] = 1
                    tmp_path.extend([next_x, next_y])
                    
    table_num_dict[table_num].append(tmp_path)

    
def board_bfs(board, board_num, x, y):
    q = collections.deque()
    q.append([x,y])
    board[x][y] = board_num
    tmp_path = [x,y]
    
    while q:
        now_x, now_y = q.popleft()
        
        for i in range(len(x_move)):
            next_x, next_y = now_x+x_move[i], now_y+y_move[i]
            if 0 <= next_x < len(board) and 0 <= next_y < len(board):
                if board[next_x][next_y] == 0:
                    q.append([next_x, next_y])
                    board[next_x][next_y] = board_num
                    tmp_path.extend([next_x, next_y])
                    
    board_num_dict[board_num].append(tmp_path)


def table_rotate(table):
    tmp_table = [[0 for y in range(len(table))] for x in range(len(table))]
    for x in range(len(tmp_table)):
            for y in range(len(tmp_table)):
                tmp_table[y][len(table)-1-x] = table[x][y]
    return tmp_table


def solution(game_board, table):
    answer = 0
    
    #table num 2부터
    table_num = 2
    for x in range(len(table)):
        for y in range(len(table)):
            if table[x][y] == 1:
                bfs(table, table_num, True, x, y)
                table_num += 1
    
    # 3번 돌림
    for i in range(3): 
        table = table_rotate(table)
        table_num_visited = []
        for x in range(len(table)):
            for y in range(len(table)):
                if table[x][y] >= 2 and table[x][y] not in table_num_visited:
                    table_num = table[x][y]
                    table_num_visited.append(table_num)
                    bfs(table, table_num, False, x, y)
                    
    #board
    board_num = 2
    for x in range(len(game_board)):
        for y in range(len(game_board)):
            if game_board[x][y] == 0:
                board_bfs(game_board, board_num, x, y)
                board_num += 1 
    
    table_num_visited = []
    for i in range(len(board_num_dict)):
        board_cmp = board_num_dict[i+2][0]
        find_answer = False
        for j in range(len(table_num_dict)):
            if (j+2) in table_num_visited:
                continue
            if find_answer == True:
                break
            for k in range(4):
                table_cmp = table_num_dict[j+2][k]    
                if len(board_cmp) != len(table_cmp):
                    break
                if len(board_cmp) == 1 and len(table_cmp) == 1:
                    answer += 1
                    find_answer = True
                    table_num_visited.append(j+2)
                    break
                
                cmp_right = True
                cmp_first, cmp_second = board_cmp[0]-table_cmp[0], board_cmp[1]-table_cmp[1]
                for l in range(2, len(board_cmp)):
                    if l%2 == 0 and board_cmp[l]-table_cmp[l] != cmp_first:
                        cmp_right = False
                        break
                    if l%2 == 1 and board_cmp[l]-table_cmp[l] != cmp_second:
                        cmp_right = False
                        break
                
                if cmp_right == True:
                    answer += len(table_cmp)//2
                    find_answer = True
                    table_num_visited.append(j+2)
                    break
            
    return answer

 

정확성  테스트
테스트 1 〉	통과 (0.97ms, 10.3MB)
테스트 2 〉	통과 (0.94ms, 10.4MB)
테스트 3 〉	통과 (1.01ms, 10.3MB)
테스트 4 〉	통과 (0.92ms, 10.3MB)
테스트 5 〉	통과 (0.96ms, 10.4MB)
테스트 6 〉	통과 (9.93ms, 10.4MB)
테스트 7 〉	통과 (12.05ms, 10.4MB)
테스트 8 〉	통과 (9.89ms, 10.3MB)
테스트 9 〉	통과 (9.53ms, 10.3MB)
테스트 10 〉	통과 (122.61ms, 10.5MB)
테스트 11 〉	통과 (172.63ms, 10.5MB)
테스트 12 〉	통과 (160.06ms, 10.6MB)
테스트 13 〉	통과 (143.38ms, 10.6MB)
테스트 14 〉	통과 (0.62ms, 10.3MB)
테스트 15 〉	통과 (0.19ms, 10.3MB)
테스트 16 〉	통과 (0.36ms, 10.5MB)
테스트 17 〉	통과 (0.46ms, 10.4MB)
테스트 18 〉	통과 (0.50ms, 10.3MB)
테스트 19 〉	통과 (0.18ms, 10.3MB)
테스트 20 〉	통과 (0.19ms, 10.3MB)
테스트 21 〉	통과 (0.12ms, 10.4MB)
테스트 22 〉	통과 (0.15ms, 10.4MB)

 

후기

 BFS를 사용한 시뮬레이션? 문제인 것 같다. 어찌어찌해서 풀긴 풀었는데 지렁이 코드가 되버렸다... 생각보다 구현할것들이 있어서 복잡했다. 시간도 생각보다 오래걸려서, 아직도 제대로 시험을 치기에는 먼 것 같다.

 

풀이

* 답인 경우를 먼저 생각해보면, '형태'는 같지만 '위치'만 다르다. 따라서 table을 4번 회전한 것에서 각각 조각들의 형태를 전부 가져오고, 이것을 board의 각 구멍에다가 직접 비교하면서 답을 찾도록 했다.

(1) 먼저 bfs를 사용하여 table의 각 조각에다가 넘버를 세겨준다. bfs로 진행할 때 , 각 조각의 x축y축 값을 딕셔너리에 따로 저정하였다.

(2) table을 회전시켜주고, 각각 bfs를 사용하여 해당하는 조각 딕셔너리에다가 x축y축 값을 저장한다.(맨 처음에 조각에 넘버를 세겨줬으므로 회전했을 경우 조각의 넘버를 찾는게 가능해졌다.)

(3) board의 각 구멍에 bfs 를 사용하여 board용 딕셔너리에 따로 구멍별 x축y축 값을 저장한다.

(4) board의 각 구멍과 table의 각 조각들(4번 회전시켜준것 모두)을 각각 비교한다. board 각 구멍의 x축y축과 table 각 조각의 x축과 y축을 하나하나씩 비교하여 맞는지 다른지를 비교할 수 있다. 예를 들어, board:[1,2][3,4]와 table:[2,3][4,5]는 비교했을 때 딱 맞다고 판별 할 수 있다. 위치만 다르고 각각 형태가 똑같기 떄문이다.