[Python] 프로그래머스 위클리 챌린지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

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

 

 

---

풀이

1. BFS 탐색을 이용해 연결된 모든 블록의 좌표를 찾아냅니다 find_board_bfs
2. 찾아낸 블록의 좌표를 최대한 왼쪽 끝으로 붙이는 작업을 합니다 change_puzzle
3. solution 함수 내에서 블록들을 돌려가며(rotate_pz)  일치하는 블록을 찾아내고 일치하는 블록이 있는경우 
   리스트에 저장한 후 총 블록의 갯수를 계산하여 리턴했습니다 

# This is a sample Python script.
 
# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.
 
 
def solution(game, table): #메인함수
    game_puzzle = [] # find_board_bfs 함수를 통해 찾은 블록들을 넣을 리스트
    table_puzzle = []
    for i in range(0, len(table)):
        for j in range(0, len(table)):
            table[i][j] = table[i][j] ^ 1 #xor 연산을 통해 table 의 0과 1을 뒤집음
    for i in game:
        while (0 in i): #0 이 존재하는 리스트 요소중에 가장 먼저있는것 부터 시작 해서 0이 없어질때까지 반복
            game_puzzle.append(find_board_bfs(game, game.index(i), i.index(0))) #bfs 로 찾은 블록들을 위에 선언한 리스트에 삽입하는 과정
    for i in table:
        while (0 in i):
            table_puzzle.append(find_board_bfs(table, table.index(i), i.index(0)))
 
    table_puzzle = change_puzzle(table_puzzle, len(table)) #chage_puzzle 함수를 통해 찾은 블록들의 좌표를 가장 왼쪽 모서리에 가깝게 붙혀줌
    game_puzzle = change_puzzle(game_puzzle, len(game))
    last = [] #일치하는 퍼즐을 보관하는 리스트
    for i in table_puzzle: #테이블에 존재하는 퍼즐을 대상으로 for문을 돌려
        if i in game_puzzle: #만약 회전X 일때도 Game_board 상에 퍼즐에 일치하는 블록이 있으면
            game_puzzle.remove(i) #Game_board 상에 퍼즐을 삭제하고
            last.append(i)#일치하는 퍼즐을 보관하는 리스트 에 조각을 추가
        else: #일치하지 않을때
            temp = list(i) #조각을 받아와
            for k in range(0, 3):
                temp = rotate_pz(temp, len(game)) #반바퀴씩 돌리는 함수 (돌리고 나서도 왼쪽끝으로 붙이는 작업 필요)
                if (sorted(temp) in game_puzzle): #만약 돌린 블록중에 일치하는게 있으면
                    game_puzzle.remove(sorted(temp))
                    last.append(sorted(temp)) #삭제 후 일치하는 퍼즐을 보관하는 리스트 에 조각을 추가
                    break # 다음 블록으로 넘어감
    answer = 0
    for i in last:
        answer = answer + len(i)  #블록의 총 면적 계산
    return answer
 
 
def change_puzzle(puzzle,max): #찾은 퍼즐의 좌표를 왼쪽끝으로 최대한 붙이는 함수
    min_x = max
    min_y = max #맥스는 블록의 최대 좌표를 뜻한다
    new_puzzle =[] #새로운 좌표를 담을 리스트
    temp =[]
    for i in puzzle:
        for j in i:
            min_x = min(min_x , j[0])
            min_y = min(min_y , j[1]) #한 퍼즐의 좌표중에서 가장 작은 x 와 y 값을 찾아서
        for k in i:
            temp.append([k[0] - min_x, k[1] - min_y]) #좌표에서 뺀다음 다시 정렬해서 새로운 좌표를 담을 리스트 new_puzzle 에 삽입
        new_puzzle.append(list(sorted(temp)))
        temp.clear()
        min_x = max
        min_y = max
 
    return (new_puzzle)
 
def rotate_pz(i , max):  #90도 씩 블록을 돌리는 함수
    rotate = [[0, 1], [-1, 0]] #변환행렬
    temp =[]
    min_x = max #또한 돌리고다시 좌표를 왼쪽끝으로 붙이는 작업을 위해
    min_y = max
    for k in i:
        temp.append([k[0] * rotate[0][0] + k[1] * rotate[0][1], k[0] * rotate[1][0] + k[1] * rotate[1][1]]) #블록을 돌린좌표를 temp 에 삽입
    for j in temp:
        min_x = min(min_x, j[0])
        min_y = min(min_y, j[1]) #위 change_puzzle 에서와 마찬가지로 가장 작은 좌표값을 찾음
    result =[]
    for k in temp:
        result.append([k[0] - min_x, k[1] - min_y]) #연산후 result 에 삽입
 
    return result
 
 
 
 
def find_board_bfs(game_board ,I , J): #bfs 을 이용해 연결된 블록을 찾는 메소드
    limit =  len(game_board)-1 #좌표평면의 최대크기
    bfs_search = [[-1,0],[1,0],[0,-1],[0,1]] #상 하 좌 우 를 뜻하는 좌표
    start = [[I ,J]] #시작 0 의 좌표을 삽입  , 큐의 역활
    board_result = [] #블록의 좌표를 넣을 곳
    game_board[start[0][0]][start[0][1]] =1 #시작 0의 좌표 임으로 이미 선택 된것으로 1로 변경
    board_result.append(start[0]) #시작 좌표를 board_result 에 삽입
    while(start): #큐가 존재할때
        temp=start.pop(0) #큐에 있는 첫번째 요소를 pop
        for i in bfs_search: #상하좌우 를 검사
            i_x =temp[0]+i[0]
            i_y =temp[1]+i[1]
            if(i_x < 0 or i_x > limit or i_y <0 or i_y > limit or game_board[i_x][i_y] ==1): #상하좌우가 막혀있거나 좌표을 넘어갔을땐 무시
                continue
            else: #상하좌우에 연결된 좌표가 있는경우
                game_board[i_x][i_y] = 1 #현재 좌표를 선택한것임으로 1로 처리
                start.append([i_x,i_y]) # 큐에 연결된 좌표를 삽입
                board_result.append([i_x,i_y]) #새로운 연결 블록의 좌표를 삽입
    return (board_result) #하나의 연결된 블록을 리턴