[백준] 17136. 색종이 붙이기 (백트래킹/Java)
·
코딩 테스트/Baekjoon
[백준] 17136. 색종이 붙이기 📌 풀이 과정큰 색종이를 먼저 붙이는 것이 효율적이므로큰 색종이로 덮을 수 있는 범위를 줄이고, 남은 작은 영역에 더 작은 색종이를 붙이도록 해야한다.그리고 색종이를 붙이는 과정에서 잘못된 선택일 경우, 다시 돌아와서 더 작은 색종이를 붙이는 로직이 필요하다.즉, 색종이를 붙이는 순서에 따라 최종 결과가 달라지기 때문에 모든 경우를 시도하는 백트래킹이 필요하다. 1️⃣ DFS 탐색(x, y) 좌표에서 색종이를 붙이면서 최소한의 색종이를 찾기 위해 재귀적으로 탐색한다.기저 조건: x >= 10에 도달하면 모든 칸을 탐색한 것이므로, 사용한 색종이 개수(usedPapers)를 최솟값으로 갱신한다.(y >= 10)일 때는 한 행을 다 탐색한 것이므로 다음 행으로 이동한다...