1. 문제 요약
- 본 문제는 game_board의 빈공간에 table의 조각을 넣어서 빈 공간을 가장 많이 채우는 조각의 개수를 묻는 문제이다.
- game_board 빈 공간에는 하나의 조각만 들어갈 수 있고, 2개의 조각을 합쳐서 넣을 수는 없다.
- table의 조각은 회전은 가능하지만, 뒤집을 수는 없다.
즉, 위와 같이 4,3번을 하나의 빈공간에 같이 넣을 수 없고, 가장 많이 조각을 넣는다면 아래와 같은 형태가 된다.
2. 접근방법
내가 처음에 생각했던 아이디어는 아래와 같다.
- bfs를 이용해서 table의 조각을 구해보자.
- 조각을 구할때, 각 조각들을 구분하기 위해 조각 번호를 매기고 딕셔너리에 저장한다.
- 각 딕셔너리에 있는 value를 3번씩 회전해서 딕셔너리에 넣는다.
- game_board와 비교하고, 알맞는게 있으면, 채워넣는다.
위의 아이디어를 구현하려고 했으나, 각 조각의 회전 결과를 구하는 과정에서 음수 좌표가 발생하게 되었다.
그 이유로 나는 회전을 시킬때, n*m 형태의 배열을 회전시키지 않고, 각 좌표값만을 회전시키려고 했기 때문에 음수 범위의 인덱스가 나타나게 된것이다.
따라서, table을 순회하면서 구한 조각은 n*m 배열 형태로 만들어서 가지고 있어야 한다는 아이디어를 추가했다. 또한, 딕셔너리를 쓰지 않고 리스트로 바꿔서 풀었다.(큰 이유는 없다. 딕셔너리로 풀는게 더 효과적이지만, 오답 코드를 지우고 새로 풀음)
최종 아이디어
- bfs를 이용해서 table의 조각을 구해보자.
- 조각을 구할때, 각 조각들을 구분하기 위해 조각 번호를 매기고 임시 리스트에 저장한다.
- table을 순회하면서 구한 조각은 n*m 배열 형태로 만들어서 가지고 있어야 한다.
- 위에서 구한 임시 리스트를 3번씩 회전해서 임시리스트에 추가로 넣는다.
- 그렇게 구한 4방향에 대한 임시 리스트를 전체 비교 리스트에 넣는다.
- game_board와 비교하고, 알맞는게 있으면, 채워넣고, 전체 비교 리스트에 해당하는 인덱스에 있는 리스트를 pop한다.3. 풀이
# 1) DFS or BFS 를 이용하여 좌표탐색을 한다 - 조각 모음을 좌표로 저장한다
# 2) 받은 좌표들을 사각형 형태로 가공한다.
# 3) 사각형 형태의 가공물들을 90도 회전하는 함수를 만든다.
# 4) 비교 및 검사
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
table_snippets = [] # table의 조각 도형이 가질수 있는 모든 경우의 수를 각 조각별로 저장한 리스트 ex: [[[직사각형 배열],[회전],[],[]], []]
visited = []
def table_bfs(new_table, table, x, y, visited):
q = deque()
q.append([x, y])
visited[x][y] = 1
new_table[x][y] = 1
n = len(table)
m = len(table[0])
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if table[nx][ny] == 1 and visited[nx][ny] == 0:
visited[nx][ny] = 1
new_table[nx][ny] = 1
q.append([nx, ny])
# 위의 BFS 과정을 통해 현재 조각들이 어떤 형태를 띄는지 알 수 있다.
new_table = del_row(new_table)
new_table = spin_90(new_table)
new_table = del_row(new_table)
# 행 삭제, -> 90도 회전 -> 행 삭제를 통해 0,0부터 시작하는 n*m 형태의 직사각형(혹은 정사각형) 배열을 생성할 수 있다.
return new_table
def table_append(table, res): # 3번 회전을 진행하여 각 회전에 따른 배열을 추출
for i in range(3):
table = spin_90(table)
res.append(table)
return res
def spin_90(table):
n = len(table)
m = len(table[0])
new_table = [[0 for _ in range(n)] for j in range(m)]
for i in range(n):
for j in range(m):
row = i
col = j
new_row = col
new_col = n - row - 1
new_table[new_row][new_col] = table[row][col]
return new_table
def del_row(table):
new_table = []
for i, val in enumerate(table):
if sum(val) != 0:
new_table.append(table[i])
return new_table
def matching(new_table, game_board, x, y, table_snippets, visited): # game_board와 table에서 뽑은 조각 목록을 비교해서 채워넣는다.
block_cnt = 1
q = deque()
q.append([x, y])
visited[x][y] = 1
new_table[x][y] = 1
n = len(game_board)
m = len(game_board[0])
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if game_board[nx][ny] == 0 and visited[nx][ny] == 0:
visited[nx][ny] = 1
new_table[nx][ny] = 1
q.append([nx, ny])
block_cnt += 1
new_table = del_row(new_table)
new_table = spin_90(new_table)
new_table = del_row(new_table)
# 한 공간에 하나의 조각을 채워넣었으면, 그 조각의 인덱스에 해당하는 리스트를 다 지운다.(한번 썼기 때문에 해당하는 조각과 회전을 해서 파생된 것들 없애줘야함)
for i, val in enumerate(table_snippets):
for j in val:
if new_table == j:
table_snippets.pop(i)
return block_cnt
return 0
def solution(game_board, table):
n = len(table)
visited = [[0 for _ in range(n)] for _ in range(n)]
# table에서 조각을 찾고, 각 조각들을 회전한 결과를 0,0을 기준으로 배열에 저장한다.
# 예로 0번째 조각 모음은 [ [1,1],[[1],[1]], [1,1], [[1], [1]] ]
for i in range(n):
for j in range(n):
if table[i][j] == 1 and visited[i][j] == 0:
new_table = [[0 for _ in range(n)] for _ in range(n)]
res_table = table_bfs(new_table, table, i, j, visited)
snippet = []
snippet.append(res_table)
res = table_append(res_table, snippet)
table_snippets.append(res)
visited = [[0 for _ in range(n)] for _ in range(n)]
cnt = 0
# 매칭을 하고, 매칭된 블럭의 수를 더한다.
for i in range(n):
for j in range(n):
if visited[i][j] == 0 and game_board[i][j] == 0:
new_table = [[0 for _ in range(n)] for _ in range(n)]
block_cnt = matching(new_table, game_board, i, j, table_snippets, visited)
cnt += block_cnt
return cnt
# print(solution([[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]]))문제가 엄청 어렵지는 않았지만, 회전을 어떻게 구현하고 처리할지, 조각들의 모양을 어떻게 관리할지를 고민해볼 수 있는 좋은 문제같다.
Backend Developer