dfs/bfs 구현 보다는 2차원 배열 처리가 까다로운 문제였다.
🤔 Thinking
우선 문제를 읽고 아래와 같이 문제 풀이 방법을 정의하였다.
1. 테이블 안의 블록 찾기
블록을 찾기 위해서는 DFS 또는 BFS 를 이용해 쉽게 구현할 수 있다. 아직 코드를 보고 잘 이해가 가지 않는 분은 음료수 얼려먹기와 같은 문제를 참고 바란다.
from collections import deque
def find_block(graph, v, n, move_to):
queue = deque([v])
block = [v]
while queue:
x, y = queue.popleft()
graph[x][y] = 0
for i, j in move_to:
xi, yj = x + i, y + j
if -1 < xi < n and -1 < yj < n and graph[xi][yj]:
block.append((xi, yj))
queue.append((xi, yj))
return block
def make_blocks(board, n):
move_to = [(1, 0), (-1, 0), (0, -1), (0, 1)]
blocks = []
for i in range(n):
for j in range(n):
if board[i][j]:
blocks.append(find_block(board, (i, j), n, move_to))
return blocks 전체 배열의 요소를 확인하면서 블록을 탐색한다. 코드가 복잡해지기에 make_blocks() 함수를 만들어 분리 시켰다.
2. 게임 보드의 빈 공간 찾기
게임 보드에서는 앞서 사용한 블록 찾기 함수를 이용해 빈칸을 찾을 수 있다. 다만 테이블과 달리 블록에서는 찾고자하는 칸이 0 이므로 1로 변환시킨다.
# 빈칸 찾기(빈칸: 1, 블록: 0 변환)
board = list(map(lambda x: list(map(lambda y: 1 - y, x)), game_board))
blanks = make_blocks(board, n)위는 1로 변환 시킨 후 make_blocks() 함수를 호출 시킨 코드이다.
3. 블록-빈 공간 매칭
해당 부분이 제일 까다로웠다😢 블록을 빈 공간에 매칭하기 위해서는 서로의 위치가 같아야 했고 블록이 회전 가능했기에 회전한 경우도 매칭을 확인해 주어야한다.
인덱스 위치 변환
1, 2 를 통해서 블록의 인덱스 값을 가져왔다. 여기서 문제는 블록과 빈공간의 위치가 다르다는 점이다. 따라서 블록과 빈공간의 위치를 0, 0 으로 시작하는 박스 형태로 변환한다.
위의 그림은 6X6 2차원 배열이다. 현재 블록의 위치는 [(3, 4), (4, 4), (5, 4), (4, 3)] 으로 저장 되어 있다.
현재 블록을 3X2 크기의 박스 형태의 크기로 저장한다.
def make_box(block):
x, y = zip(*block)
col, row = max(x) - min(x) + 1, max(y) - min(y) + 1
box = [[0] * row for _ in range(col)]
for i, j in block:
i, j = i - min(x), j - min(y)
box[i][j] = 1
return boxx 축, y 축 의 길이를 계산하여 (0, 0) 에서 시작하는 배열을 만든다.
결과: [[0, 1], [1, 1], [0, 1]]
블록 회전
3X3 의 간단한 2차원 배열에서 오른쪽 방향으로 90도 회전 한다고 생각해보자.
위 그림에서 1행은 마지막 열로 이동하고, 2번째 행은 2번째 열, 3번째행은 1번째 열로 이동한 것을 확인할 수 있다.
1행을 index(row, col) 형태로 정리하면 아래와 같다.
(0, 0), (0, 1), (0, 2) => (0, 2), (1, 2), (2, 2)
규칙을 찾아보면 i, j 를 각각 행과 열이라고 할 때 아래와 같다.
회전 후 row = j
회전 후 col = 마지막 인덱스(2) - i
위 방식을 이용해 시계방향으로 90도 회전하는 함수를 작성하였다.
def rotate_block(block):
cnt = 0
rotate_block = [[0]*len(block) for _ in range(len(block[0]))]
for i in range(len(block)):
for j in range(len(block[0])):
if block[i][j]: # 블록의 크기를 반환하기 위해 더해준다.
cnt += 1
rotate_block[j][len(block)-1-i] = block[i][j]
return rotate_block, cnt💻 전체 코드
위 방식대로 블록과 빈칸을 찾고 박스 형태로 만들어서 총 4번 회전하면서 빈칸과 블록이 일치하는 지 확인하였다.
from collections import deque
def find_block(graph, v, n, move_to):
queue = deque([v])
block = [v]
while queue:
x, y = queue.popleft()
graph[x][y] = 0
for i, j in move_to:
xi, yj = x + i, y + j
if -1 < xi < n and -1 < yj < n and graph[xi][yj]:
block.append((xi, yj))
queue.append((xi, yj))
return block
def make_blocks(board, n):
move_to = [(1, 0), (-1, 0), (0, -1), (0, 1)]
blocks = []
for i in range(n):
for j in range(n):
if board[i][j]:
blocks.append(find_block(board, (i, j), n, move_to))
return blocks
def make_box(block):
x, y = zip(*block)
col, row = max(x) - min(x) + 1, max(y) - min(y) + 1
box = [[0] * row for _ in range(col)]
for i, j in block:
i, j = i - min(x), j - min(y)
box[i][j] = 1
return box
def rotate_block(block):
cnt = 0
rotate_block = [[0]*len(block) for _ in range(len(block[0]))]
for i in range(len(block)):
for j in range(len(block[0])):
if block[i][j]: # 블록의 크기를 반환하기 위해 더해준다.
cnt += 1
rotate_block[j][len(block)-1-i] = block[i][j]
return rotate_block, cnt
def match_blank(blank, blocks):
for i, block in enumerate(blocks):
block = make_box(block)
for _ in range(4):
block, cnt = rotate_block(block) # 블록 회전
if blank == block:
del blocks[i]
return cnt
return 0
def solution(game_board, table):
answer = 0
n = len(table)
blocks = make_blocks(table, n) # 블록 찾기
# 빈칸 찾기(빈칸: 1, 블록: 0 변환)
board = list(map(lambda x: list(map(lambda y: 1 - y, x)), game_board))
blanks = make_blocks(board, n)
# 빈칸-블록 매치(박스 만들기 매칭)
for blank in blanks:
blank = make_box(blank)
answer += match_blank(blank, blocks)
return answer📕 참고 문헌
다음의 링크를 참고했습니다.
https://school.programmers.co.kr/learn/courses/30/lessons/84021
https://www.youtube.com/watch?v=PqzyFDUnbrY
