#17136 색종이 붙이기

출처:https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

 

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

 

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

 

풀이

dfs를 사용하여 해결하였다. map에 1인 부분을 색종이로 겹치지 않게 덮으면 되는데 색종이의 개수는 각 사이즈마다 5개로 한정돼있다. 총 4개의 함수를 만들어서 구현하였다. 메인으로 동작하는 dfs함수, 그리고 해당 맵에 크기가 몇인 색종이까지 붙일 수 있는지 int값을 리턴해주는 check_size함수, check_size함수를 직관적으로 보기 쉽게 map에 해당 색종이를 붙일 수 있는지 없는지 bool형으로 리턴해주는 함수, 마지막으로 특정 사이즈의 색종이를 2차원 배열에 방문표시해주는 fill_visit함수로 이루어져있다.

 

큰 동작과정은 다음과 같다.dfs함수를 실행하면 먼저 크기가 몇인 색종이까지 덮을 수 있는지 check_size함수로 확인한다. 그래서 해당 크기의 색종이 사용횟수가 5개 미만이라면 fill_visit함수로 visit배열을 채워주고 카운트값을 올려 다음으로 진행시킨다.  다음에도 위와같은 과정을 반복하는데 만약 현재위치가 이미 방문이 돼 있다면 (색종이로 덮어져 있는 곳이라면 그냥 카운트값만 올리고 색종이를 붙이는 과정은 스킵하면 된다. 그러다가 카운트 개수가 map의 모든 1의 개수와 같아지면 사용한 색종이를 합하여 기존의 최솟값과 비교하여 저장한다. 

그리고 다음 재귀함수로 넘겨준때 시간초과를 막는 핵심적인 방법이 있다. 현재까지 붙이 종이개수가 기존의 최솟값보다 같거나 크면 굳이 다음 상황을 진행할 필요가 없으므로 바로 리턴시켜주면 시간을 효율적으로 줄일 수 있다.

 

코드