◾ 퍼즐 조각 채우기 : 프로그래머스 LEVEL 3
문제
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
- 조각은 한 번에 하나씩 채워 넣습니다.
- 조각을 회전시킬 수 있습니다.
- 조각을 뒤집을 수는 없습니다.
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다.
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.
- 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
- 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.
최대한 많은 조각을 채워 넣으면 총 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에는 반드시 하나 이상의 블록이 놓여 있습니다.
출력
- 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return
입출력 예
| 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. 해설
- DFS(또는 BFS)를 통해 빈 칸과 블록의 좌표를 기록하여 비교하면 된다.
- 블록은 회전시킬 수 있으므로 회전을 4번 시키며 각 경우를 비교한다.
- 계산 시간을 줄이고 싶다면 list가 아닌 dict으로 빈 칸을 저장하면 된다.
2. 프로그램
- game_board를 탐색하며 빈 칸을 체크한다.
- dfs를 통해 좌표를 기록한다.
- 총 4회 회전시키며 table를 탐색하여 블록을 체크한다.
- dfs를 통해 좌표를 기록한다.
- block의 값과 비교하여 동일한 기록이 있는 경우 해당 블록으로 채운다.
# 코드
import copy
def dfs(graph, r, c, p, n, num):
result = [p]
for d_r, d_c in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
new_r, new_c = r + d_r, c + d_c
if 0 <= new_r < n and 0 <= new_c < n and graph[new_r][new_c] == num:
graph[new_r][new_c] = 2
result += dfs(graph, new_r, new_c, [p[0]+d_r, p[1]+d_c], n, num)
return result
def rotate(table, n):
result = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
result[i][j] = table[n-j-1][i]
return result
def solution(game_board, table):
answer = 0
n = len(game_board)
block = []
for i in range(n):
for j in range(n):
if game_board[i][j] == 0:
game_board[i][j] = 2
result = dfs(game_board, i, j, [0, 0], n, 0)
block.append(result)
for _ in range(4):
table = rotate(table, n)
table_copy = copy.deepcopy(table)
for i in range(n):
for j in range(n):
if table_copy[i][j] == 1:
table_copy[i][j] = 2
result = dfs(table_copy, i, j, [0, 0], n, 1)
if result in block:
block.pop(block.index(result))
answer += len(result)
table = copy.deepcopy(table_copy)
else:
table_copy = copy.deepcopy(table)
return answer
후라이드 치킨