상세 컨텐츠

본문 제목

퍼즐 조각 채우기

코딩테스트/구현

by 수타. 2023. 6. 30. 16:03

본문

 

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

'코딩테스트 > 구현' 카테고리의 다른 글

드래곤 커브  (0) 2023.07.26
기둥과 보 설치  (0) 2023.07.19
프렌즈4블록  (0) 2023.06.28
  (0) 2023.06.15
자물쇠와 열쇠  (0) 2023.06.12

관련글 더보기