2차원 블록들을 가장 효율적으로 묶는 방법
조회수 370회
가로와 세로가 w, h인 2차원 블록 평면에 각 사이즈가 같은 블록들이 있습니다. 각 블록은 각자 고유한 값을 가지고 있으며 대각선을 제외한 상하좌우로 연결될수 있습니다. 블록들을 주어진 갯수만큼 연결하여 블록평면 위의 모든 블록이 소외되지 않게 묶어야합니다. 이때 묶인 블록들은 그 같은 묶음의 블록중 가장 낮은 값이 되어서 블록 고유값을 일부 손실하게 됩니다. 모든 블럭을 일정 길이만큼 묶으면서 가장 손실이 낮은 구성을 찾아야하는 문제인데 어디서 어떻게 접근해야할지 잘 모르겠습니다.
지금까지 시도한 부분은 가능한 블록연결의 형태를 미리 구성한 패턴을 만들어서 가장 낮은값부터 패턴을 대입해서 차례로 평면을 만드는 방법을 구현해보았지만 실행시간이 너무 오래걸렸습니다. DFS방식에 문제가 있는것 같아서 패턴을 대입한 부분에 우선순위 큐를 써서 bfs 형식을 구현했지만 실행시간을 맞출수가 없었습니다. 모든 블럭의 경우를 찾아서 그래프 형태로 구성하는 것도 생각했는데 역시 오래 걸릴것 같습니다. 혼자서 풀려고 했지만 시간이 너무 오래걸릴것 같아 질문하게되었습니다
많은 지도 부탁드립니다
댓글 입력