2차원 블록들을 가장 효율적으로 묶는 방법

조회수 370회

가로와 세로가 w, h인 2차원 블록 평면에 각 사이즈가 같은 블록들이 있습니다. 각 블록은 각자 고유한 값을 가지고 있으며 대각선을 제외한 상하좌우로 연결될수 있습니다. 블록들을 주어진 갯수만큼 연결하여 블록평면 위의 모든 블록이 소외되지 않게 묶어야합니다. 이때 묶인 블록들은 그 같은 묶음의 블록중 가장 낮은 값이 되어서 블록 고유값을 일부 손실하게 됩니다. 모든 블럭을 일정 길이만큼 묶으면서 가장 손실이 낮은 구성을 찾아야하는 문제인데 어디서 어떻게 접근해야할지 잘 모르겠습니다.

지금까지 시도한 부분은 가능한 블록연결의 형태를 미리 구성한 패턴을 만들어서 가장 낮은값부터 패턴을 대입해서 차례로 평면을 만드는 방법을 구현해보았지만 실행시간이 너무 오래걸렸습니다. DFS방식에 문제가 있는것 같아서 패턴을 대입한 부분에 우선순위 큐를 써서 bfs 형식을 구현했지만 실행시간을 맞출수가 없었습니다. 모든 블럭의 경우를 찾아서 그래프 형태로 구성하는 것도 생각했는데 역시 오래 걸릴것 같습니다. 혼자서 풀려고 했지만 시간이 너무 오래걸릴것 같아 질문하게되었습니다

많은 지도 부탁드립니다

  • 무슨 알고리즘 과제인 것 같은데, 이렇게 문제만 그대로 복사하는 것은 이런 포럼에 적당한 질문이라고 생각하지 않습니다. 아무리 멍청하고 부끄러운 것이라도 자신의 생각이 있었을 거 아닙니까? 그걸 글로 풀어서 질문해보는 것이 중요하다고 생각합니다. 글로 써보면서 정리되고 발전되는 부분도 있고요. nowp 2019.11.18 12:37
  • 급하게 질문하느라 그런 부분은 미처 생각하지 못했습니다 김한길 2019.11.18 12:41

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)