퍼즐 조각 채우기
https://school.programmers.co.kr/learn/courses/30/lessons/84021
문제 설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
- 조각은 한 번에 하나씩 채워 넣습니다.
- 조각을 회전시킬 수 있습니다.
- 조각을 뒤집을 수는 없습니다.
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.
3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.
최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.
현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.
풀이
크게 보면 DFS/BFS와 도형 회전을 사용해 문제를 해결
- 도형 분리
BFS를 이용해board와table에서 각각의 도형을 분리합니다.
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def find_block(arr, num, N):
re = []
visited = [[False]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if not visited[i][j] and arr[i][j] == num:
dq = deque([(i,j)])
arr[i][j] = num ^ 1
visited[i][j] = True
lst = [(i, j)]
while dq:
x, y = dq.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= N or ny < 0 or ny >= N :
continue
elif arr[nx][ny] == num:
dq.append((nx, ny))
arr[nx][ny] = num ^ 1
visited[nx][ny] = True
lst.append((nx, ny))
re.append(lst)
return re- 각 뽑아낸 도형을 정규화(?) 합니다.
각 도형을 뽑으면 같은 모형이어도 다른 (x,y)값을 가집니다.
위 예시의 2번은board의 [(0,2),(0,3),(1,3),(2,3),(2,4)]에 들어가지만, [(0,3),(0,4),(1,4),(2,4),(2,5)]로 다른 값을 가집니다.
위 두 칸들은 0부터 시작하는 2차원 배열로 변경해 서로 비교할 수 있게 해줍니다.
def two_arr(arr):
# 최대 - 최소 +1 === 행 열 수
x = [i[0] for i in arr]
y = [i[1] for i in arr]
c, r = max(x) - min(x) + 1, max(y) - min(y) + 1
re = [[0]*r for _ in range(c)]
for i, j in arr:
i, j = i - min(x), j - min(y)
re[i][j] = 1
return re- 도형 회전
def rotate90(arr) :
new_arr = [[0]*len(arr) for _ in range(len(arr[0]))]
count = 0
for i in range(len(arr)):
for j in range(len(arr[i])):
if arr[i][j] == 1:
count += 1
new_arr[j][len(arr)-i-1] = arr[i][j]
return new_arr, count- 전체 코드
위 함수들을 종합해 문제를 풉니다.
from collections import deque
def rotate90(arr) :
new_arr = [[0]*len(arr) for _ in range(len(arr[0]))]
count = 0
for i in range(len(arr)):
for j in range(len(arr[i])):
if arr[i][j] == 1:
count += 1
new_arr[j][len(arr)-i-1] = arr[i][j]
return new_arr, count
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def find_block(arr, num, N):
re = []
visited = [[False]*N for _ in range(N)]
for i in range(N):
for j in range(N):
if not visited[i][j] and arr[i][j] == num:
dq = deque([(i,j)])
arr[i][j] = num ^ 1
visited[i][j] = True
lst = [(i, j)]
while dq:
x, y = dq.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= N or ny < 0 or ny >= N :
continue
elif arr[nx][ny] == num:
dq.append((nx, ny))
arr[nx][ny] = num ^ 1
visited[nx][ny] = True
lst.append((nx, ny))
re.append(lst)
return re
def two_arr(arr):
# 최대 - 최소 +1 === 행 열 수
x = [i[0] for i in arr]
y = [i[1] for i in arr]
c, r = max(x) - min(x) + 1, max(y) - min(y) + 1
re = [[0]*r for _ in range(c)]
for i, j in arr:
i, j = i - min(x), j - min(y)
re[i][j] = 1
return re
def solution(board, table):
answer = 0
# 분리
sep_b = find_block(board, 0, len(board))
sep_t = find_block(table, 1, len(table))
for b in sep_b:
isFill = False
two_b = two_arr(b) # 2차원 배열
for t in sep_t:
if isFill == True:
break
two_t = two_arr(t)
for i in range(4):
two_t, cnt = rotate90(two_t)
if two_t == two_b:
answer += cnt
sep_t.remove(t)
isFill = True
break
return answer