풀다가 집중력도 떨어지고 오래걸렸던 문제다 :(
기초만 풀다가 살짝 복잡비스무리 해졌다고 다른 해설도 안읽혀서 다른사람들은 어떻게 풀었는지 모르겠지만 아마 나보다는 효율적이지 않을까,,,,
문제
풀이
1.game_board에서 빈칸 좌표를 찾는 함수를 만든다 (bfs)
- bfs로 탐색하면서 빈칸 좌표들을 찾으면 된다. 이부분만 간단(?) 했다
2.table에서 색칠된 부분 좌표를 찾는 함수를 만들어야 하는데 이부분은 1번 부분하고 같은 함수를 사용한다
- 여기서 포인트는 game_board는 0으로 된부분을 찾아야하고, table은 1로된 부분을 찾아야한다 그래서 함수를 호출할때 0,1을 변수로 받았다
get_shapes 라는 함수를 만들어서 사용했는데 함수를 호출할때 num에 1인지 0인지 넣어준다
board는 game_board랑 table정보를 받아서 사용했다
def get_shapes(q, num, board)# game_board의 빈칸좌표를 구하는 부분
for x in range(len(game_board)):
for y in range(len(game_board[0])):
q.append([x,y])
shapes = get_shapes(q, 0, game_board) # 0인 부분이 빈칸이다
# table의 색칠된 좌표를 구하는 부분
for x in range(len(table)):
for y in range(len(table[0])):
q.append([x,y])
shapes = get_shapes(q, 1, table) # 1인 부분이 색칠된 도형이다3.색칠된 도형의 좌표 리스트들을 먼저 구해둔다
- table의 색칠된 좌표를 먼저 전부 구해둔다
shapes = get_shapes(q, 1, table)
if shapes: # 각 색칠된 도형의 좌표를 구할때마다 다른 리스트에 넣어서 하나의 리스트로 만든다
coloured_shapes.append(shapes) 이 부분을 거치면 문제 예시에서는 이러한 리스트가 만들어진다
[
[[0, 0], [1, 0]],
[[0, 3], [0, 4], [1, 4], [2, 4], [2, 5]],
[[1, 2], [2, 2], [3, 2], [2, 1]],
[[4, 0], [4, 1], [5, 1]],
[[4, 3], [4, 4]]
]
- 위의 리스트안에 좌표들의 90, 180, 270 도 회전 된 좌표까지 구한다
- 회전 좌표를 구하면서 각 도형마다 1번부터 번호를 메기고 도형 번호만 저장하는 리스트를 만들어준다 (나중에 색칠된 모양은 1개인데 같은 모양 빈칸이 여러개일때를 방지하기 위해 써먹을꺼다)
- 여기서 좌표는 무조건 0,0 기준에 맞춘다
1)예를들어 도형의 좌표가 [(3,-1),(3,0),(4,0)] 이면 x도 0기준, y도 0기준으로 맞춰준다
2)x좌표들의 min_x, y좌표들의 min_y을 찾아준다 (이 값들은 rotate할때 구해주면 된다)
3)모든 좌표들을 x-min_x, y-min_y를 해주면 0,0에 가장 가까워진다
( [ (3-3, -1-(-1)),(3-3, 0-(-1)),(4-3, 0-(-1)) ] -> [(0,0),(0,1),(1,1)] )
def rotate(coords):
degrees = [90,180,270,0]
rotated_shapes = [] # rotate된 좌표들을 넣어준다
keys = []# 몇번 도형인지 - 중복방지
for idx, shapes in enumerate(coords): #모양 하나하나 돌아주고(예시에서는 5개)
for degree in degrees: # 90, 180, 270도로 회전
rad = degree * (math.pi / 180.0)
new_coords = []
min_x = 50
min_y = 50
for coord in shapes:# 하나의 모양에 좌표가 여러개임
x, y = coord
nx = round(math.cos(rad)*x - math.sin(rad)*y)
ny = round(math.sin(rad)*x + math.cos(rad)*y)
new_coords.append([nx, ny])
# 0,0 에 가깝게 맞춰주기 위해 구해둔다
min_x = min(min_x, nx)
min_y = min(min_y, ny)
# 0,0 에 최대한 가깝게 맞춘 좌표를 구한다
new_coords = [[sublist[0] - min_x, sublist[1] - min_y] for sublist in new_coords]
# sorted 를 해야 같은 좌표의 순서가 달라지지 않는다 (아래와 같은 상황 방지)
# [[0, 0], [0, 1], [1, 0]] != [[0, 0], [1, 0] ,[0, 1]]
rotated_shapes.append(sorted(new_coords))
# 각 도형들이 담겨있는 리스트의 인덱스를 도형 번호로 사용한다
keys.append(idx)
return rotated_shapes, keys여기서 keys리스트를 살펴보면 아래와 같은 리스트가 나온다
[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]
총 5개의 모양이 있고 각각 원래모양, 90, 180, 270도 회전, 이렇게 각 모양마다 좌표가 4개씩 있기 때문이다
4.game_board의 빈칸 좌표들을 구하면서 색칠된 도형 리스트에서 넣을수있는 모양이 있는지 체크한다
이 부분은 좌표를 한번에 전부 구하는게 아니라 모양 하나의 좌표를 구할때마다 넣을 도형이 있는지 체크하고 있으면 좌표 리스트의 길이를 카운트 한다
#각 모양의 좌표를 구할때마다
shapes = get_shapes(q, 0, game_board)
# 빈칸모양도 0,0 기준으로 바꾸자
if shapes:
min_x= min(sublist[0] for sublist in shapes)
min_y = min(sublist[1] for sublist in shapes)
shapes = [[sublist[0] - min_x, sublist[1] - min_y] for sublist in shapes]
if sorted(shapes) in rotated_shapes: #먼저 구해둔 색칠된 도형들의 리스트에 있는지 체크하고
cnt += len(shapes) # 넣을수 있으니 칸의 갯수를 세준다 (좌표의 갯수 == 칸의 갯수)
shapes_idx = rotated_shapes.index(sorted(shapes)) #내가 만들어둔 도형번호가 몇번인지 확인
# 인덱스를 살펴보면 0번 도형은 0*4+0 ~ 0*4+3 이런식이다
# 인덱스 나누기 4를 했을때 몫이 도형의 번호다
# 그래서 반대로 그 몫에 +0 +1 +2 +3 을 하면 4개의 인덱스를 모두 알 수 있다
val = shapes_idx // 4
del rotated_shapes[val*4:(val*4)+4] # 사용한 도형은 회전한 좌표까지 총 4개를 모두 리스트에서 지워준다 (중복방지)
어휴 쓰면서도 헷갈리네
5.하나의 코드로 만들면 된다
from collections import deque
import math
def rotate(coords): #회전해서 최대한 0,0 에 가깝게 맞춘다
degrees = [90,180,270,0]
rotated_shapes = []
keys = []# 몇번 도형인지 - 중복방지
for idx, shapes in enumerate(coords): #모양 하나하나
for degree in degrees:
rad = degree * (math.pi / 180.0)
new_coords = []
min_x = 50
min_y = 50
for coord in shapes:# 하나의 모양에 좌표가 여러개임
x, y = coord
nx = round(math.cos(rad)*x - math.sin(rad)*y)
ny = round(math.sin(rad)*x + math.cos(rad)*y)
new_coords.append([nx, ny])
min_x = min(min_x, nx)
min_y = min(min_y, ny)
new_coords = [[sublist[0] - min_x, sublist[1] - min_y] for sublist in new_coords]
rotated_shapes.append(sorted(new_coords))
keys.append(idx)
return rotated_shapes, keys
def get_shapes(q, num, board): # table일때는 1이 도형 아닐때는 0 이 도형
dx = [-1,1,0,0]
dy = [0,0,-1,1]
#shapes = []
empty_board = []
while q:
x, y = q.popleft()
if board[x][y] == num:
empty_board.append([x,y])
# 0 -> 1, 1 -> 0 으로 바꿔줘야함
if num == 1:
board[x][y] = 0
else:
board[x][y] = 1
for i in range(len(dx)):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<len(board) and 0<=ny<len(board[0]) and board[nx][ny] == num:
q.append([nx, ny])
return empty_board
def solution(game_board, table):
dx = [-1,1,0,0]
dy = [0,0,-1,1]
q = deque()
shapes = []
cnt = 0
# 테이블 도형 리스트 미리 뽑아놓기
coloured_shapes = []
for x in range(len(table)):
for y in range(len(table[0])):
q.append([x,y])
shapes = get_shapes(q, 1, table)
if shapes:
coloured_shapes.append(shapes)
rotated_shapes, keys = rotate(coloured_shapes)
# #빈칸찾아서 도형 있는지 보기
for x in range(len(game_board)):
for y in range(len(game_board[0])):
q.append([x,y])
shapes = get_shapes(q, 0, game_board)
# 빈칸모양도 0,0 기준으로 바꾸자
if shapes:
min_x= min(sublist[0] for sublist in shapes)
min_y = min(sublist[1] for sublist in shapes)
shapes = [[sublist[0] - min_x, sublist[1] - min_y] for sublist in shapes]
if sorted(shapes) in rotated_shapes:
shapes_idx = rotated_shapes.index(sorted(shapes))
val = shapes_idx // 4
del rotated_shapes[val*4:(val*4)+4]
cnt += len(shapes)
return cnt이 문제는 bfs구현은 간단했는데 어떻게 같은 도형인지 찾는게 제일 복잡했다
다른사람들은 어케 풀었는지 봐야겠다
이건 너무 복잡해,,,,,
