https://school.programmers.co.kr/learn/courses/30/lessons/84021
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제요약:
board판이 있고 puzzle판이 있을때 딱 puzzle이 board의 빈칸에 딱맞는경우만 낄수 있다고 했을때, 가장 많이 낀다면 그때의 블럭 수를 구하여라.
소요시간:
1시간 10분
난이도 3
코딩:
#퍼즐 개개인 분류
dy = [-1,0,1,0]
dx = [0,1,0,-1]
#DFS로 한 블럭마다 체크
def DFS(arr,y,x,t):
if arr[y][x] == 1:
#t로 바꾸고
arr[y][x] = t
for i in range(4):
ny = y +dy[i]
nx = x +dx[i]
if 0<=ny<len(arr) and 0<=nx<len(arr[0]) :
DFS(arr,ny,nx,t)
return 1
else:
return 0
#찾은 블럭의 추출
def find_XY(arr,t):
X = []
Y = []
for y in range(len(arr)):
for x in range(len(arr[0])):
if arr[y][x] == t:
X.append(x)
Y.append(y)
return t,min(X),min(Y),max(X),max(Y)
#회전
def rotate(arr):
arr = [i for i in zip(*arr[::-1])]
return arr
#추출한 좌표로 퍼즐만들기
def find_cube(arr):
t=2
for y in range(len(arr)):
for x in range(len(arr[0])):
if DFS(arr,y,x,t):
t+=1
cubes = []
for k in range(2,t):
t,x1,y1,x2,y2 = find_XY(arr,k)
cubes.append([[arr[y][x] for x in range(x1,x2+1)] for y in range(y1,y2+1)])
return cubes
#비교를 위해 다 1로 바꾸기
def change_1(arr):
temp = [[0] *len(arr[0]) for _ in range(len(arr))]
for y in range(len(arr)):
for x in range(len(arr[0])):
if arr[y][x] !=0:
temp[y][x] = 1
return temp
def solution(game_board, table):
#game_board는 0이 빈곳이었지만 코드의 편리를 위해 1로 변경
for y in range(len(game_board)):
for x in range(len(game_board[0])):
if game_board[y][x] == 1:
game_board[y][x] = 0
else:
game_board[y][x] = 1
puzzles = find_cube(table)
cubes = find_cube(game_board)
ans = 0
for puzzle in puzzles:
#네번 회전
piv = 0
for _ in range(4):
puzzle = rotate(puzzle)
#만약 큐브와 puzzle이 같다면
#이때 앞순서 부터 했을 때 지운다면 for 함수에 끝이 index를 초과할 수 있기 때문에, 뒤에서 부터 탐색
for i,cube in enumerate(cubes[::-1]):
if change_1(cube)==change_1(puzzle):
piv = 1
ans += sum([j for i in change_1(cube) for j in i])
break
if piv:
del cubes[len(cubes)-i-1]
break
return ans
물론 puzzle하나 하나를 찾고 구분하는데는 DFS를 사용했지만, 그것보다 나머지 비교하고 문제를 이해하는것이 더 큰 비중이 있는 문제라고 생각해, 구현파트에 넣었습니다.
저의 풀이방법은 양쪽에서 DFS를 통해 각 퍼즐 하나하나를 구분하고 양쪽에서 각각 퍼즐을 추출한뒤 그두개가 같을 때, 체크를 하는 방법으로 진행했습니다. 다만 이때 추출할때 좌표를 이용해 board에서 puzzle을 하나하나 추출했는데 이때 만약 [[2,0,1],[0,0,1],[1,1,1]]과같이 최대최소값을 추출한 사각형안에 다른 사각형이 있을 수 있으므로, change1에서 1로 바꿀때 0이아니면 1로 바꾸는것이 아닌 t값이라면 1로 바꿔야 더 정확한 풀이가 될거같습니다.
테스트케이스에 해당 케이스가없어 통과했습니다.
아래가 수정한 코드이며, 다음에 풀땐 좀더 빨리 구현할 필요가 있어보입니다.
#퍼즐 개개인 분류
dy = [-1,0,1,0]
dx = [0,1,0,-1]
#DFS로 한 블럭마다 체크
def DFS(arr,y,x,t):
if arr[y][x] == 1:
#t로 바꾸고
arr[y][x] = t
for i in range(4):
ny = y +dy[i]
nx = x +dx[i]
if 0<=ny<len(arr) and 0<=nx<len(arr[0]) :
DFS(arr,ny,nx,t)
return 1
else:
return 0
#찾은 블럭의 추출
def find_XY(arr,t):
X = []
Y = []
for y in range(len(arr)):
for x in range(len(arr[0])):
if arr[y][x] == t:
X.append(x)
Y.append(y)
return t,min(X),min(Y),max(X),max(Y)
#회전
def rotate(arr):
arr = [i for i in zip(*arr[::-1])]
return arr
#추출한 좌표로 퍼즐만들기
def find_cube(arr):
t=2
for y in range(len(arr)):
for x in range(len(arr[0])):
if DFS(arr,y,x,t):
t+=1
cubes = []
for k in range(2,t):
t,x1,y1,x2,y2 = find_XY(arr,k)
cubes.append((t,[[arr[y][x] for x in range(x1,x2+1)] for y in range(y1,y2+1)]))
return cubes
#비교를 위해 다 1로 바꾸기
def change_1(t,arr):
temp = [[0] *len(arr[0]) for _ in range(len(arr))]
for y in range(len(arr)):
for x in range(len(arr[0])):
if arr[y][x] ==t:
temp[y][x] = 1
return temp
def solution(game_board, table):
#game_board는 0이 빈곳이었지만 코드의 편리를 위해 1로 변경
for y in range(len(game_board)):
for x in range(len(game_board[0])):
if game_board[y][x] == 1:
game_board[y][x] = 0
else:
game_board[y][x] = 1
puzzles = find_cube(table)
cubes = find_cube(game_board)
ans = 0
for t,puzzle in puzzles:
#네번 회전
piv = 0
for _ in range(4):
puzzle = rotate(puzzle)
#만약 큐브와 puzzle이 같다면
#이때 앞순서 부터 했을 때 지운다면 for 함수에 끝이 index를 초과할 수 있기 때문에, 뒤에서 부터 탐색
for i,cube in enumerate(cubes[::-1]):
if change_1(cube[0],cube[1])==change_1(t,puzzle):
piv = 1
ans += sum([j for i in change_1(cube[0],cube[1]) for j in i])
break
if piv:
del cubes[len(cubes)-i-1]
break
return ans