https://school.programmers.co.kr/learn/courses/30/lessons/84021?language=python3
빈 칸을 1과 0으로 표시한 2차원 배열과, 조각을 1과 0으로 표시한 2차원 배열을 주고 맞는 모양 최대한 끼워 맞추기 하는 문제이다.
문제의 조건은 조각은 한 번에 하나씩, 조각 회전만 가능, 새로 끼워넣은 조각 옆에 빈 칸이 있으면 안 된다는 것이다.
처음에 보고 조각 두 개로 빈 칸 하나 채우는 경우도 있지 않을까 싶어 포기할 까 했는데 마지막 조건 때문에 할만 해진 것 같다.
전략
접근 전략은 최초에는 BFS로 빈 칸과 조각을 통계 내고 사이즈 같은 빈 칸과 조각을 매칭하고 조각을 회전 시키면서 모양을 맞추려고 했다.
그런데 아무리 고민해도 조각을 회전시키는 방법이 떠오르지가 않았다. 조각마다 회전하는 중심이 다르고 특히 2 n 배열 같은 경우 중심이 특정 점이 아니라서 엄청 복잡해질 것 같았다.
그러다가 생각해낸 것이 어차피 주어지는 2차원 배열은 n n 배열이니까 저거 자체를 회전시켜서 회전된 조각도 구하는 방법이다.
결론
- 최초에 조각 배열을 상하좌우 대칭으로 180도 돌아간 배열을 구한다.
- 90도 돌리는 함수를 만들어서 각 배열로 90도, 270도 돌아간 배열을 구함으로써 회전 조각을 전부 구한다.
- BFS를 통해서 각 조각을 찾아낸 다음 평행이동 시켰을 때 일치하는 모양이 있는지 찾는다.
90도 돌리는 함수
def rotate90(arr, length):
returnArr = [[0] * length for _ in range(length)]
for i in range(length):
for j in range(length):
returnArr[j][length-i-1] = arr[i][j]
return returnArr
열의 순서 => 행의 순서, 행의 순서 뒤집은 것 => 열의 순서로 함으로써 90도 돌아간 배열을 얻을 수 있었고 이거를 3번 반복했다.
BFS
def bfs(i, j, chk, limit, visited, board):
queue = [(i, j)]
idx = 0
visited[i][j] = False
while idx < len(queue):
y, x = queue[idx]
idx += 1
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if 0 <= ny < limit and 0 <= nx < limit
and board[ny][nx] == chk and visited[ny][nx]:
visited[ny][nx] = False
queue.append((ny, nx))
queue.sort()
return queuedeque를 사용하지 않고 idx를 증가시킴으로써 더 이상 탐색할 칸이 없을 때 while문을 벗어나도록 했다. 이렇게하면 탐색한 기록이 queue에 다 남아서 나중에 찾기 편했다. 마지막에는 탐색 기록을 정렬함으로써 나중에 조각끼리 비교하기 쉽게 만들었다.
파라미터의 chk는 table이랑 game_board랑 1, 0의 의미가 달라서 그거 구분해주기 위해 넣었다.
조각 탐색
limit = len(game_board)
visited_game = [[True] * limit for _ in range(limit)]
visited_table = [[True] * limit for _ in range(limit)]
visited_table_90 = [[True] * limit for _ in range(limit)]
visited_table_180 = [[True] * limit for _ in range(limit)]
visited_table_270 = [[True] * limit for _ in range(limit)]
table_90 = rotate90(table, limit)
table_180 = rotate90(table_90, limit)
table_270 = rotate90(table_180, limit)
game = [[] for _ in range(limit * limit + 1)]
blocks = [[] for _ in range(limit * limit + 1)]table을 90, 180, 270도 돌려주었고 탐색을 위해 각각 visited배열을 만들어주었다.
game, blocks 배열은 조각 크기별로 정리하기 위해서 2차원 배열로 만들었다.
조각 맞추기
for i in range(len(game)):
# 크기가 i인 빈 칸과 조각이 있을 때
if game[i] and blocks[i]:
for g in game[i]: # 크기가 i인 조각 여러 개 중 하나
for j in range(len(blocks[i])): # 돌린 조각 전체 돌면서 비교하기
b = blocks[i][j]
# 한 번 사용한 조각은 날릴 것.
if b:
found = True
# 평행 이동 거리 기준
dy = g[0][0] - b[0][0]
dx = g[0][1] - b[0][1]
for s in range(i):
# 한 칸이라도 평행이동 거리 다르면 정지
if dy != g[i][0] - b[i][0] or dx != g[i][1] - b[i][1]:
found = False
break
# 일치하는 조각 찾으면 해당 조각 빈 칸 처리
if found:
blocks[i][j] = []
ans += 1조각 크기별로 돌면서 조각이 있을 때, 같은 크기의 각 빈 칸 별로 또 조각이 돌면서 평행이동 한 거리가 모든 칸에 대해서 일치하는지 비교했다. 그러고 일치하는 조각이 나오면 빈 배열로 날려줬는데 그런데 막혔다.
일치하는 조각에 대해서 회전한 모양 전부 다 날려야하는데 그거를 어떻게 찾을지 모르겠다.
팁
저기서 막혀 있었는데 팁을 얻었다. 2차원 배열 회전시키는 공식을 사용하면 조각 자체를 회전 시킬 수 있다고 하던데 테이블 회전 시킨 함수를 테이블 전체가 아니라 조각에 적용할 수 있을 것 같다는 생각이 들었다.
def rotate90(arr, length):
for i in range(len(arr)):
y, x = arr[i]
arr[i] = (x, length - y - 1)회전하는 함수를 이렇게 바꿨고 table 전체 돌리던 코드는 전부 삭제했다. 이제는 원래 테이블에서 조각을 찾은 후 각 조각별로 회전시키면서 일치여부를 확인할 예정이다.
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
def rotate90(arr, length):
for i in range(len(arr)):
y, x = arr[i]
arr[i] = (x, length - y - 1)
arr.sort()
def bfs(i, j, chk, limit, visited, board):
queue = [(i, j)]
idx = 0
visited[i][j] = False
while idx < len(queue):
y, x = queue[idx]
idx += 1
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if 0 <= ny < limit and 0 <= nx < limit and board[ny][nx] == chk and visited[ny][nx]:
visited[ny][nx] = False
queue.append((ny, nx))
queue.sort()
return queue
def solution(game_board, table):
answer = 0
limit = len(game_board)
visited_game = [[True] * limit for _ in range(limit)]
visited_table = [[True] * limit for _ in range(limit)]
game = [[] for _ in range(limit * limit + 1)]
blocks = [[] for _ in range(limit * limit + 1)]
for i in range(limit):
for j in range(limit):
if game_board[i][j] == 0 and visited_game[i][j]:
tmp = bfs(i, j, 0, limit, visited_game, game_board)
game[len(tmp)].append(tmp)
if table[i][j] == 1 and visited_table[i][j]:
tmp = bfs(i, j, 1, limit, visited_table, table)
blocks[len(tmp)].append(tmp)
for i in range(limit * limit + 1):
# 크기가 i인 빈 칸과 조각이 있을 때
if game[i] and blocks[i]:
for g in game[i]: # 크기가 i인 조각 여러 개 중 하나
for j in range(len(blocks[i])): # 크기가 같은 조각 전체와 비교하기
b = blocks[i][j]
# 한 번 사용한 조각은 날릴 것.
if b:
for t in range(4): # 4번 회전 하는 동안 일치 여부 확인
found = True
# 평행 이동 거리 기준
dy = g[0][0] - b[0][0]
dx = g[0][1] - b[0][1]
for s in range(i):
# 한 칸이라도 평행이동 거리 다르면 정지
if dy != g[s][0] - b[s][0] or dx != g[s][1] - b[s][1]:
found = False
rotate90(b, limit)
break
if found:
break
# 일치하는 조각 찾으면 해당 조각 빈 칸 처리
if found:
blocks[i][j] = []
answer += i
break
return answer