위클리 챌린지 #4. 퍼즐 조각 채우기

(문제 설명)

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

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

 

---

(문제 해설)

이 문제는 빡센 구현 문제입니다.

 

0. 굳이 따지자면 bfs라고 볼 수 있겠지만, 저는 이 문제를 그냥 구현 문제라고 봅니다.

1. 제가 풀이할 방법은 table에 주어진 도형들을 각 도형이 들어가는 일종의 틀을 만들어서 각각 보관합니다.

2. game_board를 돌면서 주어진 규칙에 맞는지 즉, 해당 빈 공간에 도형이 다 채워지는 체크하고 채워지면 +1을 하는 식으로 풀 예정입니다.

 

3. table을 돌면서 도형들의 좌표값들을 리턴 합니다. (좌표 전체를 돌면서 좌표가 1이라면 bfs탐색을 합니다.

단, 이 1값이 not visit일 때만 탐색을 하겠죠.

# 1. 도형의 좌표들을 리턴
def bfs(i, j, table, chk):
    puz = []
    n = len(table)
    q = [(i, j)]
    chk[i][j] = True
    while q:
        x, y = q.pop()
        puz.append([x, y])
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if not (0 <= nx < n and 0 <= ny < n):
                continue
            if not chk[nx][ny] and table[nx][ny] == 1:
                q.append([nx, ny])
                chk[nx][ny] = True
    return puz

4. 뽑아낸 좌표들을 틀에 맞게 넣는 작업입니다. 틀에 넣으면서 다시 도형은 1, 빈 공간은 0이 됩니다.

# 2. 좌표들을 틀에 맞게 저장하고, 다시 0, 1의형태로 변환
def changeState(puzSt):
    rowMin, rowMax = 100, -1
    colMin, colMax = 100, -1
    for st in puzSt:
        row, col = st
        rowMin = min(rowMin, row)
        rowMax = max(rowMax, row)
        colMin = min(colMin, col)
        colMax = max(colMax, col)

    rowLength = rowMax - rowMin + 1
    colLength = colMax - colMin + 1

    chaSt = [[0] * colLength for _ in range(rowLength)]
    for st in puzSt:
        x = st[0] - rowMin
        y = st[1] - colMin
        chaSt[x][y] = 1

    return chaSt

rowLength = rowMax - rowMin + 1 이렇게 계산을하면 주어진 도형이 들어가는 틀의 최대 row 값을 구할 수 있습니다

col도 마찬가지죠.

 

5. 이렇게 퍼즐들을 리스트에 저장합니다

6. 이제 game_board를 순회하면서 빈공간을 만나면 아까 저장했던 도형들을 넣어보면서 딱 크기에 맞는지 체크하는 로직을 짜고, 맞다면 도형의 크기를 +n 해주면 됩니다.

# 빈칸 없이 채워졌는지 체크
def isFillUp(puz, game_board):
    n = len(game_board)
    row = len(puz)
    col = len(puz[0])
    # 퍼즐의 크기만큼 체크
    for i in range(n - row + 1):
        for j in range(n - col + 1):
            Fill = True
            for x in range(row):
                for y in range(col):
                    game_board[x + i][y + j] += puz[x][y]
                    if game_board[x + i][y + j] != 1:
                        Fill = False

            if isEmpty(game_board, puz, i, j):
                Fill = False

            if Fill:
                return True

            else:  # 다시 비우고 이동하면 체크하는 것
                for x in range(row):
                    for y in range(col):
                        game_board[x + i][y + j] -= puz[x][y]
    return False

# 주위에 빈칸이 있는지 없는지 체크 (참일 경우 비어있는것)
def isEmpty(g_b, puz, i, j):
    n = len(g_b)
    for x in range(len(puz)):
        for y in range(len(puz[0])):
            if puz[x][y] == 1:
                for k in range(4):
                    nx = x + i + dx[k]
                    ny = y + j + dy[k]
                    if not (0 <= nx < n and 0 <= ny < n):
                        continue
                    if g_b[nx][ny] != 1:
                        return True
    return False

---

[ 코드 ]

 

# 4. 퍼즐 조각 채우기
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


# 주위에 빈칸이 있는지 없는지 체크 (참일 경우 비어있는것)
def isEmpty(g_b, puz, i, j):
    n = len(g_b)
    for x in range(len(puz)):
        for y in range(len(puz[0])):
            if puz[x][y] == 1:
                for k in range(4):
                    nx = x + i + dx[k]
                    ny = y + j + dy[k]
                    if not (0 <= nx < n and 0 <= ny < n):
                        continue
                    if g_b[nx][ny] != 1:
                        return True
    return False


# 빈칸 없이 채워졌는지 체크
def isFillUp(puz, game_board):
    n = len(game_board)
    row = len(puz)
    col = len(puz[0])
    # 퍼즐의 크기만큼 체크
    for i in range(n - row + 1):
        for j in range(n - col + 1):
            Fill = True
            for x in range(row):
                for y in range(col):
                    game_board[x + i][y + j] += puz[x][y]
                    if game_board[x + i][y + j] != 1:
                        Fill = False

            if isEmpty(game_board, puz, i, j):
                Fill = False

            if Fill:
                return True

            else:  # 다시 비우고 이동하면 체크하는 것
                for x in range(row):
                    for y in range(col):
                        game_board[x + i][y + j] -= puz[x][y]
    return False


# 90도 회전
def rotation(puzzle):
    n = len(puzzle)
    m = len(puzzle[0])
    res = [[0] * n for _ in range(m)]
    for r in range(n):
        for c in range(m):
            res[c][n - 1 - r] = puzzle[r][c]
    return res

# 1. 도형의 좌표들을 리턴
def bfs(i, j, table, chk):
    puz = []
    n = len(table)
    q = [(i, j)]
    chk[i][j] = True
    while q:
        x, y = q.pop()
        puz.append([x, y])
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if not (0 <= nx < n and 0 <= ny < n):
                continue
            if not chk[nx][ny] and table[nx][ny] == 1:
                q.append([nx, ny])
                chk[nx][ny] = True
    return puz

# 2. 좌표들을 틀에 맞게 저장하고, 다시 0, 1의형태로 변환
def changeState(puzSt):
    rowMin, rowMax = 100, -1
    colMin, colMax = 100, -1
    for st in puzSt:
        row, col = st
        rowMin = min(rowMin, row)
        rowMax = max(rowMax, row)
        colMin = min(colMin, col)
        colMax = max(colMax, col)

    rowLength = rowMax - rowMin + 1
    colLength = colMax - colMin + 1

    chaSt = [[0] * colLength for _ in range(rowLength)]
    for st in puzSt:
        x = st[0] - rowMin
        y = st[1] - colMin
        chaSt[x][y] = 1

    return chaSt


def solution(game_board, table):
    ans = 0
    length = len(game_board)
    chk = [[False] * length for _ in range(length)]
    puzSum = []
    puzzles = []
    for i in range(length):
        for j in range(length):
            if table[i][j] == 1 and not chk[i][j]:
                # 1. 도형의 좌표들을 리턴
                puzState = bfs(i, j, table, chk)
                # 2. 좌표들을 크기에 맞게 저장하고, 다시 0, 1의형태로 변환
                puz = changeState(puzState)
                # 3. 퍼즐 목록에 추가
                puzzles.append(puz)
                # 4. 퍼즐 길이 목록에 추가
                puzSum.append(len(puzState))

    for i, p in enumerate(puzzles):
        # 4 방향 회전
        for _ in range(4):
            p = rotation(p)
            if isFillUp(p, game_board):
                ans += puzSum[i]
                break
    return ans

---

후기

 

퍼즐들의 좌표를 찾을때는 bfs를 이용하니까 bfs문제라고 할지도 모르겠다.

하지만 필자는 이문제를 정말 좋은 힘든 구현 문제라고 생각합니다.