[프로그래머스] 위클리 챌린지 3주차 - 퍼즐 조각 채우기 (Python)

코딩 테스트 연습 - 퍼즐 조각 채우기 [위클리 챌린지 3주차]

코딩테스트 연습 - 3주차

문제를 천천히 읽어보면 설명을 왜 그렇게 어렵게 적어놨나 싶네요..ㅎㅎ

물론 쉽지 않은 문제였고 프로그래머스에서 Python으로 알고리즘을 풀며 코드가 가장 길었던 문제였던 것 같네요ㅎㅎ

 

풀이

문제를 해결한 방법을 간단하게 말하면 아래와 같습니다.

1. board의 빈 공간과 table의 block을 찾아서 각각 list와 dict에 저장

2. 찾은 빈 공간과 block을 (0, 0)에 가장 가깝게 이동

3. 찾은 빈 공간들과 block들을 90도씩 4번 회전시킨 값들 중에서 min값으로 변환

4. 빈 공간과 block이 같은 배열인지를 확인

 

먼저 문제의 설명을 보면 한 차례에 하나의 block을 넣을 수 있고 새로 채워 넣은 block 주변에 빈 공간이 있으면 안 된다고 합니다.

\( \Rightarrow \) 빈 공간과 block의 크기와 모양이 같아야 한다.

 

그러면 각각의 빈공간과 block의 크기와 모양을 어떻게 저장하고 비교해야 할까요?

배열에 담겨있는 상태에서는 각각 다른 좌표를 가지고 있어서 회전과 비교가 굉장히 까다롭죠.

1. board의 빈공간과 table의 block을 찾아서 각각 list와 dict에 저장

그래서 먼저 빈공간과 block을 찾기 위해서 저는 BFS탐색 알고리즘을 이용해서 각각의 좌표들을 list로 만들어 저장했습니다.

 

좌표들의 배열인 상태에서도 좌표들이 모두 다르기에 아직도 비교하기가 까다롭습니다  

그래서 각각의 크기와 모양을 비교하기 위해 (2) 번과 (3) 번을 진행합니다.

 

2. 찾은 빈 공간과 block을 (0, 0)에 가장 가깝게 이동

\( \Rightarrow \) (2) 번은 좌표 단위로 비교하기 위해 (0, 0)에 가장 가깝게 이동시키는 것이고 (3) 번은 (0, 0)에 가깝게 이동시켜서 해당 상태에서 90도 회전시킨 것들을 배열에 저장해서 그중에서 min값을 반환합니다.

3. 찾은 빈 공간들과 block들을 90도씩 4번 회전시킨 값들 중에서 min값으로 변환

그렇게 되면 같은 크기에 같은 모양이지만 회전이 다른 ㄴ모양과 ㄱ 모양의 block을 입력으로 넣으면 같은 ㄴ의 형태만 반환되는 것과 같은 효과를 낼 수 있는 것이죠. 

 

4. 빈 공간과 block이 같은 배열인지를 확인

위의 과정을 거치고 나면 회전에 상관없이 같은 크기와 같은 모양을 가졌다면 같은 좌표들을 가지고 있을 것입니다.

\( \Rightarrow \) 간단하게 빈공간 == block을 진행해서 같은 배열이라면 answer에 크기를 더해주면 문제를 해결할 수 있습니다.

 

 

Code

from collections import defaultdict, deque
def getShape(board, target, row, col):
    visit, blen = set([(row, col)]), len(board)
    queue = deque([(row,col)])
    while queue:                        # BFS 탐색
        y, x = queue.popleft()
        for r, c in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = y+r, x+c
            if 0<=nr<blen and 0<=nc<blen and (nr,nc) not in visit and board[nr][nc] == target:
                queue.append((nr, nc))
                visit.add((nr,nc))
    return list(visit)

def move_zero(block):               # (0, 0)에 가장 가깝게 이동
    values = list(map(list, zip(*block)))
    minr, minc = min(values[0]), min(values[1])
    return sorted([(r-minr, c-minc) for r, c in block])     # 이동후에 정렬하여 반환

def rotate(block):                  # 4번 회전시켜서 min값을 반환
    if len(block)==1: return block
    block = move_zero(block)
    values = list(map(list, zip(*block)))
    size = max(max(values[0]), max(values[1])) + 1
    grid_block = [[0]*size for _ in range(size)]    # 정사각형의 2차원 배열
    for row, col in block:          # block 좌표를 grid 형태로 변환
        grid_block[row][col] = 1

    candi = [block]
    for step in range(3):           # 3번 반복
        temp = [[0]*size for _ in range(size)]      # 회전결과를 담을 2차원 배열
        for r in range(size):       # 회전
            for c in range(size):
                temp[c][size-1-r] = grid_block[r][c]
        for r in range(size):       # 좌표단위로 변환
            flag = 0
            for c in range(size):
                if temp[r][c] == 1:
                    visit = getShape(temp, 1, r, c)
                    flag = 1
                    break
            if flag == 1:break
        shape = move_zero(visit)    # (0, 0)에 가깝게 이동
        candi.append(shape)
        grid_block = temp
    return min(candi)

def find_location(board, table):
    blen = len(board)
    location, bvisit = [], set()                # board의 빈공간을 담을 배열
    tdict, tvisit = defaultdict(list), set()    # block을 담을 dict
    for row in range(blen):
        for col in range(blen):
            if board[row][col] == 0 and (row,col) not in bvisit:    # board의 빈공간일 때
                bshape = getShape(board, 0, row, col)
                for v in bshape:
                    bvisit.add(v)
                bshape = rotate(bshape)
                location.append(bshape)         # 회전된 빈공간의 형태 저장
            if table[row][col] == 1 and (row,col) not in tvisit:    # block일 때
                tshape = getShape(table, 1, row, col)
                for v in tshape:
                    tvisit.add(v)
                tshape = rotate(tshape)
                tdict[len(tshape)].append(tshape)   # 회전된 block의 크기에 맞게 저장
    return location, tdict

def solution(game_board, table):
    answer = 0
    location, tdict = find_location(game_board, table)
    for loca in location:                       # board의 빈공간을 반복
        k = len(loca)
        if k not in tdict:continue
        for tidx, shape in enumerate(tdict[k]): # 같은 크기의 block 비교
            if loca == shape:
                answer += k
                del tdict[k][tidx]
                break
    return answer

 

 

문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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_board	table	result
[[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

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