1. 문제
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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에는 반드시 하나 이상의 블록이 놓여 있습니다.
- 키워드
- 로직 구현 설계를 정말 정말
제발...꼼꼼하게 해보도록 하자.
2. 풀이
이 문제는 어떠한 알고리즘을 요구하기보다,
그냥 주어진 문제를 어떻게 해결하는 지 능력을 물어보는 거 같다.
키워드에서 요구했듯, 로직 구현을 정말 잘 해야 한다.
먼저, 나는 다음과 같은 과정을 진행해 구현하였다.
- spin 이라는 배열을 90도 시계방향으로 회전시키는 기능을 먼저 구현한다.
- table에서 퍼즐조각을 꺼내는 로직을 구현한다.
- 구현 방법은 다음 과정을 거친다.
1. table과 똑같은 크기의 2차원 배열을 만든다.
2. table에서 BFS를 통해 퍼즐조각을 찾고, 2차원 배열에 저장한다.
3. 2차원 배열에서 모든 열이 0인 행을 삭제한다.
4. spin을 사용해 배열을 90도 회전한다.
5. 한 번 더 모든 열이 0인 행을 삭제한다.
6. spin을 3번 더 하고 return (안해도 된 다. 어차피 회전시키면서 비교하기 때문)
- 구현 방법은 다음 과정을 거친다.
- 퍼즐 조각을 모두 꺼냈다면, game_board에서 빈 칸을 찾는다.
- 여기서도 몇 가지 과정이 필요하다.
- BFS를 통해서 최소 row, col값과 최대 row, col값을 구한다.
ex) 문제 예시를 보자면,
1번 블록을 비교할 때 시작점과 끝점이 맞아야 하기 때문이다.쟤 때문에 몇 번이나 샷건쳤다. - 퍼즐 조각의 가로, 세로 길이와 (최대 col-최소 col +1),(최대 row-최소 row +1) 값이 같다면 비교를 한다. (안 맞는다면 퍼즐조각을 회전 하고 1,2 과정을 4번 반복한다.)
- 비교하고 딱 들어맞는다면 퍼즐조각의 가장 첫 부분(piece[0][0])을 -1로 바꾸고 결과에 더한다. (중복방지)
해당 문제를 이 과정으로 풀었지만, 반례가 존재하는 거 같다.
프로그래머스에서 정답이 뜨긴 했지만, 조금 더 세세하게 봐야할 거 같다.
이 문제를 풀 때, 몇 가지 주의사항이 있다.
주의사항
- 퍼즐조각을 찾을 때, 특정 위치에서 방향을 저장하는 방식을 사용하면 오답이 뜰 확률이 있다.
예제로 다음과 같은 퍼즐조각이 있다고 가정하자.
BFS를 할 때, 12시 방향부터 시계방향으로 탐색한다고 가정할 때, 방향은 다음과 같이 저장된다.
노란색 퍼즐조각 : 우,우,하,우,우
초록색 퍼즐조각 : 우,우,하,우,우
이런 경우가 생기기 때문에, 가끔 조각이 맞지도 않는데 맞다고 뜨는 경우가 있을 것이다.
퍼즐조각을 뽑아낼 때, 방향을 저장한다면, 주의할 필요가 있다.
- 빈 칸과 퍼즐조각을 비교할 때, 빈 칸에서 시작해서는 안 된다.
해당 문제에서 최소 row, col과 최대 row, col을 구하는 이유다.
문제의 테스트 케이스에서도 확인 할 수 있다.
해당 블록을 1번 블록과 비교한다고 하였을 때, 빈 칸에서 비교를 시작하면 이렇게 진행 될 것이다.
때문에, 빈 칸을 BFS로 탐색해 현재 찾은 빈칸에서 최대 row, col과 최소 row, col을 구해서
최소 row,col ~최대 row, col 까지 비교만 하면 된다.
3. 소스코드
# python
from collections import deque
d = [[-1,0],[0,1],[1,0],[0,-1]]
def spin(block):
spin_block = [[0]*len(block) for _ in range(len(block[0]))]
for row in range(len(block)):
for col in range(len(block[0])):
spin_block[col][len(spin_block[0])-1-row] = block[row][col]
return spin_block
def catch_piece(table,row,col):
R,C = len(table),len(table)
piece = [[0]*C for _ in range(R)]
piece[row][col] = 1
q = deque([[row,col]])
while q:
r,c = q.popleft()
piece[r][c] = 1
table[r][c] = 0
for i in d:
dr,dc = i
if 0 <= r+dr < R and 0 <= c+dc < C:
if table[r+dr][c+dc] == 1:
table[r+dr][c+dc] = 0
piece[r+dr][c+dc] = 1
q.append([r+dr,c+dc])
r_piece = []
for i in piece:
if sum(i) != 0:
r_piece.append(i)
r_piece = spin(r_piece)
c_piece = []
for i in r_piece:
if sum(i) != 0:
c_piece.append(i)
for _ in range(3):
c_piece = spin(c_piece)
return c_piece
def compare(game_board,piece,row,col):
R,C = len(game_board),len(game_board)
cnt = 0
for r in range(len(piece)):
for c in range(len(piece[0])):
if piece[r][c] == 1 and game_board[row+r][col+c] == 2:
cnt += 1
elif piece[r][c] == 0 and game_board[row+r][col+c] == 1:
continue
else:
return 0
return cnt
def solution(game_board,table):
answer = 0
piece = deque()
R,C = len(game_board),len(game_board)
for row in range(R):
for col in range(C):
if table[row][col] == 1:
piece.append(catch_piece(table,row,col))
for row in range(R):
for col in range(C):
if game_board[row][col] == 0:
q = deque([[row,col]])
min_row,max_row = row,row
min_col,max_col = col,col
while q:
r,c = q.popleft()
game_board[r][c] = 2
for i in d:
dr,dc = i
if 0 <= r+dr < R and 0 <= c+dc < C:
if game_board[r+dr][c+dc] == 0:
q.append([r+dr,c+dc])
min_row,max_row = min(min_row,r+dr),max(max_row,r+dr)
min_col,max_col = min(min_col,c+dc),max(max_col,c+dc)
game_board[r+dr][c+dc] = 2
result = 0
for p in range(len(piece)):
for _ in range(4):
if piece[p][0][0] == -1:
break
if len(piece[p]) == max_row-min_row+1 and len(piece[p][0]) == max_col-min_col+1:
result = compare(game_board,piece[p],min_row,min_col)
if result > 0:
answer += result
piece[p][0][0] = -1
break
piece[p] = spin(piece[p])
if result > 0:
break
return answer
if __name__ == "__main__":
print(solution([[0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0], [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0], [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1], [0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0], [0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1], [0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0], [0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0], [1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0], [0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1], [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0]],[[1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1], [1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0], [0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1], [1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1], [0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1], [1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1], [1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1], [1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1]])) # correct : 54
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]]) # correct : 14
//java 작성 준비중
4. 후기
java
준비중
python
블록의 저장방식이 잘못되었을 때,
로직은 맞으나, 너무 과도하게 굴렸을 때,
현재,
난이도도 난이도지만 뭔가 너무 힘들었다.
딱히 알고리즘적으로 요구한 건 없었으나, 구현능력과 문제해결 능력부분에서 부족한 점이 많은 거 같다.
알고리즘 문제도 중요하지만, 구현능력 관련 문제를 많이 풀어서 문제해결 능력을 길러야 할 거 같다.
이걸 JAVA로 또 풀생각을 하려니 앞이 캄캄하다...
푸는데 얼마나 걸렷어용?