[알고리즘][4] 퍼즐 조각 채우기
2023. 9. 21. 10:56ㆍ알고리즘 풀이
문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
조각은 한 번에 하나씩 채워 넣습니다.
조각을 회전시킬 수 있습니다.
조각을 뒤집을 수는 없습니다.
게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다.
puzzle_5.png
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.
puzzle_6.png
3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.
puzzle_7.png
최대한 많은 조각을 채워 넣으면 총 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
입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.
puzzle_9.png
입출력 예 #2
블록의 회전은 가능하지만, 뒤집을 수는 없습니다.
나의 풀이
- 코드를 깔끔하게 짜려고 노력했다.
- 그렇게 되니까 디버깅하기도 더 수월했던 거 같다.
- 이런 복잡한 문제는 코드가 길어질 수밖에 없는데 이렇게 되면 필시 디버깅이 어려워진다.
- 따라서 디버깅을 잘하기 위해서는 코드를 깔끔하게 짤 필요가 있다.
- 한가지 아쉬운 점은 rotation할 때 오류가 났는데 이게 아마 i, j라고 해서 헷갈린 거 같다. 이걸 x, y라고 명확하게 해주자!
- 또 하나 배운 점은 lambda (x,y):와 같이 튜플로 받는 건 안되더라. 대신에 튜플로 받고 싶으면 lambda x: x[1], x[0] 이런 식으로 인덱싱을 활용해야 한다.
- 또 하나 헤맨 점은 지나간 곳은 값이 갱신이 되어야 하는데 이를 놓쳤었다. 그래서 무한 루프가 돌았다.
- 또 하나 헤맨 점은 if not () or A에서 True를 얻고 싶다면 or을 해줘야 되는데 and를 해줘서 out of index가 발생했다.
from collections import deque
from copy import deepcopy
def solution(game_board, table):
# 그래프 + 구현 문제
# 구현에 탐색이 필요
# 블록의 모양을 결정할 역할, 블록을 돌리는 역할
def bfs(graph, start, criteria):
q = deque()
q.append(start)
start_x, start_y = start
if graph[start_y][start_x] != criteria:
return None
graph[start_y][start_x] = abs(criteria - 1)
block = []
block.append(start)
dx = [-1, 1, 0, 0]
dy = [0, 0 ,-1, 1]
while q:
cur_x, cur_y = q.popleft()
n = len(graph)
for i in range(4):
nx = cur_x + dx[i]
ny = cur_y + dy[i]
if not (0<=nx<n and 0<=ny<n) or graph[ny][nx] != criteria:
continue
graph[ny][nx] = abs(criteria - 1)
block.append((nx, ny))
q.append((nx, ny))
origin_x, origin_y = block[0]
block = list(map(lambda x: (x[0] - origin_x, x[1] - origin_y), block))
return block
n = len(game_board)
copy_game_board = deepcopy(game_board)
spaces = []
for i in range(n):
for j in range(n):
block = bfs(copy_game_board, (i, j), 0)
if block != None:
spaces.append(block)
def rotation(graph):
rotated_graph = deepcopy(graph)
n = len(graph)
for i in range(n):
for j in range(n):
rotated_graph[j][i] = graph[i][n-1-j]
return rotated_graph
answer = 0
prev_graph = deepcopy(table)
for _ in range(4):
prev_graph = rotation(prev_graph)
cur_graph = deepcopy(prev_graph)
n = len(cur_graph)
for i in range(n):
for j in range(n):
block = bfs(cur_graph, (i, j), 1)
if block != None:
if block in spaces:
prev_graph = deepcopy(cur_graph)
spaces.remove(block)
answer += len(block)
else:
cur_graph = deepcopy(prev_graph)
return answer
- lambda는 다음과 같이 unzip을 활용하면 x, y로도 표현할 수 있다.
origin_x, origin_y = block[0]
block_x, block_y = zip(*block)
block = list(map(lambda x, y: (x - origin_x, y - origin_y), block_x, block_y))
'알고리즘 풀이' 카테고리의 다른 글
[알고리즘] 개인정보 수집 유효기간 (0) | 2023.09.29 |
---|---|
[알고리즘][5] 더 맵게 (0) | 2023.09.22 |
[알고리즘][4] 전력망을 둘로 나누기 (0) | 2023.09.20 |
[알고리즘][4][X] 더 맵게 (0) | 2023.09.19 |
[알고리즘] 최솟값 구하기 (0) | 2023.09.18 |