문제
설명
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 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에는 반드시 하나 이상의 블록이 놓여 있습니다.
입력
game_board
table
아이디어
엄... 아이디어는 바로 나오지만 구현을 열심히 해야할 것 같은 문제...
가장 쉽게 접근하면
- bfs로 table에서 조각들을 분리.
- game_board를 순회하면서 끼워맞춰보기, 회전해서 총 4번 (회전해서 같다면 제외)
이러면 bfs의 시간복잡도는 무시하더라도, 보드를 조각개수*4 만큼 순회해야하므로
보드 길이 최대값이 50이라 안될 건 없어보이긴 하다.
만약 N이 매우 크다면 내가 생각한 접근은 game_board_piece class를 조각 길이와 조각의 맵 값을 가지게 짠 뒤
game_board를 0에 대한 bfs로 조각을 G개를 찾고, 조각의 길이에 따라 piece class를 해쉬
# 예를 들어 입력 예제의 제일 좌상단의 조각이라면
A = game_board_piece()
A.length = 2
A.Map = set([[1,1]])
board_hash = {2:[A,B,...] ,
5:[C,D,E,...],
...
}이런 느낌으로, 그리고 table_piece class를 짠 뒤 마찬가지로 조각길이와 조각 맵 (회전시 조각맵까지 총 4개) 를 가지게 한다. 마찬가지로 table_hash를 짠다
# 테이블 예제의 제일 좌상단 조각이라면
table_A = table_piece()
table_A.length = 2
table_A.Map = Set(
[[1,1]],
[[1],[1]]
)
table_hash = {2:[table_A,table_B,...] ,
5:[table_C,table_D,table_E,...],
...
}
이러면 board_hash와 table_hash의 같은 key에 대해서만 비교를 진행하면 되어서
비교에 대한 시간복잡도는 매우 줄 것이다. 매칭이 되면 두 딕셔너리에서 해당 인스턴스들을 삭제 length는 어차피 bfs를 하면서 쉽게 구해지고...
다만 아직 감잡기가 어려운 점은
이런 블록을 생성할때, 3x3을 Map으로 잡아야하는데 bfs로 아웃풋을 구할때 어떻게 저 사이즈를 맞출지,
이 블록에 대해서는 3x2 Map을 잡고, 회전시엔 2x3을 잡아주어야한다. 총 4개 필요
bfs를 구현할 때, 아웃풋으로 길이와 bfs가 방문한 좌표를 받아, r 좌표 low와 max, c 좌표 low와 max를 기준으로 새로운 Map을 만들고, 좌표를 기준으로 1을 채운뒤. 회전 4개를 반환... 어지럽다 벌써
어차피 제일 간단한 방법이나 이거나 핵심 구현은 비슷하므로 이 방법으로 시간을 오래 잡고 차근차근 하나씩 구현해보아야겠다.
그래서 이 방법이 간단한 방법보다 효율적인가?
큰 차이점은 bfs를 table과 맵에 대해서 2번한다는 것과 조각을 채울 때 비교 수가 매우 준다는 것?
시간 복잡도는 bfs에서는 대강 모든 조각의 길이의 합만큼 나올 것으로 예상되며
비교 과정에서는 앞서 언급한 이 최악의 경우 에만 나오지 않을까 예상 중.
일단 차근차근 구현이나 해보자...
구현
먼저 조각의 묶음을 뽑을 bfs를 구현 board의 종류에 따라 0인 값을 뽑아야할 때가 있고,
1일 때를 뽑아야할 때가 있어서 flag를 사용.
def bfs(x,y,N,board):
if board == game_board:
flag = True
else:
flag = False
Map = board
coords = [[x,y]]
Q = deque([[x,y]])
if flag:
while Q:
x,y = Q.popleft()
for _ in range(4):
nx,ny = x+dx[_], y+dy[_]
if N>nx>=0 and N>ny>=0 and not Map[nx][ny]:
Map[nx][ny] = 1
Q.append([nx,ny])
coords.append([nx,ny])
else:
while Q:
x,y = Q.popleft()
for _ in range(4):
nx,ny = x+dx[_], y+dy[_]
if N>nx>=0 and N>ny>=0 and Map[nx][ny]:
Map[nx][ny] = 0
Q.append([nx,ny])
coords.append([nx,ny])
return coords조각의 좌표값들만 묶음으로 나온다.
coords를 piece 모양으로 만들어주는 makepiece 함수 구현
def makepiece(coords):
min_x = min_y = float('inf')
max_x = max_y = 0
for _ in coords:
max_x = max(_[0],max_x)
max_y = max(_[1], max_y)
min_x = min(_[0],min_x)
min_y = min(_[1],min_y)
piece = [[0]*(max_y-min_y+1) for _ in range(max_x-min_x+1)]
for _ in coords:
piece[_[0]-min_x][_[1]-min_y] = 1
return piece시연 결과
5
110
010
011
2
1
1
3
11
10
4
010
111
3
01
11
1
1
예제에서 조각길이와 조각 모양을 담은 모습. 잘된다!
board_piece 클래스와 board_pieces dictionary를 짜자
class board_piece:
def __init__(self,piece):
self.piece = piece
def __str__(self):
return '\n'.join(''.join(str(x) for x in y) for y in self.piece)
...
board_pieces = defaultdict(list)
...
board_pieces[len(coords)].append(board_piece(piece))
print(board_pieces[5][0])
# 길이가 5인 첫번째 피스를 확인
# 결과
110
010
011이제 같은 짓을 table에 대해서 반복하는데 table_piece 클래스에서는 회전도 포함.
class table_piece:
def __init__(self,piece):
self.piece = self.getrotate(piece)
def getrotate(self,piece):
def rotate(piece):
r, c = len(piece), len(piece[0])
ret = [[0]*(r) for _ in range(c)]
for x in range(c):
for y in range(r):
ret[x][y] = piece[r-1-y][x]
return ret
pieces = [piece]
for _ in range(3):
new_piece = rotate(pieces[-1])
if new_piece in pieces:
break
pieces.append(new_piece)
return piecesgetrotate 함수는 piece를 시계방향 90도 돌려보면서 pieces와 비교하여 새로운 piece면 넣는다.
조각이 선대칭인 경우, 2번 회전하면 어차피 그 뒤론 끝,
점 대칭인 경우 1번만 회전해도 똑같아서 끝나기에 break를 걸어준다.
결과 확인
print(table_pieces[4][0]) #길이가 4인 table 조각의 첫번째 프린트
01
11
01
010
111
10
11
10
111
010회전한 조각이 모두 잘 나온다!
이제 드디어 마지막으로 비교를 해주면 끝. 여기서 부턴 효율적인 비교방법을 잘 모르겠어서... 그냥 visit boolean 리스트를 사용하였다...
anw = 0
for i, b_p in board_pieces.items():
for j, t_p in table_pieces.items():
if i == j:
b_visit = [True]*len(b_p)
t_visit = [True]*len(t_p)
for ii, x in enumerate(b_p):
for jj, y in enumerate(t_p):
if x.piece in y.piece and b_visit[ii] and t_visit[jj]:
anw += i
b_visit[ii] = False
t_visit[jj] = False
return anw결과와 느낀 점
정확성 테스트
테스트 1 〉 통과 (0.29ms, 10.6MB)
테스트 2 〉 통과 (0.31ms, 10.6MB)
테스트 3 〉 통과 (0.28ms, 10.5MB)
테스트 4 〉 통과 (0.27ms, 10.6MB)
테스트 5 〉 통과 (0.29ms, 10.6MB)
테스트 6 〉 통과 (1.62ms, 10.6MB)
테스트 7 〉 통과 (1.52ms, 10.5MB)
테스트 8 〉 통과 (1.61ms, 10.5MB)
테스트 9 〉 통과 (1.30ms, 10.6MB)
테스트 10 〉 통과 (7.08ms, 10.6MB)
테스트 11 〉 통과 (7.23ms, 10.5MB)
테스트 12 〉 통과 (7.67ms, 10.6MB)
테스트 13 〉 통과 (7.24ms, 10.6MB)
테스트 14 〉 통과 (0.26ms, 10.6MB)
테스트 15 〉 통과 (0.08ms, 10.6MB)
테스트 16 〉 통과 (0.12ms, 10.6MB)
테스트 17 〉 통과 (0.16ms, 10.5MB)
테스트 18 〉 통과 (0.16ms, 10.6MB)
테스트 19 〉 통과 (0.08ms, 10.5MB)
테스트 20 〉 통과 (0.08ms, 10.5MB)
테스트 21 〉 통과 (0.05ms, 10.4MB)
테스트 22 〉 통과 (0.05ms, 10.6MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0
다른 추천 코드들 보다 코드는 확실히 길긴한데... 속도는 잘나와서 기분이 좋네요...
이런 긴 구현을 한두번씩 해봐야, 좀 풀이가 긴 문제를 만났을 때 멘붕이 없을 것 같습니다 호호.
