[백준 2630번] 색종이 만들기 (java)

2630번: 색종이 만들기

 

색종이를 계속 4등분으로 분할하여 모두 같은 색으로 이루어졌는지 아닌지를 확인하는 문제.

분할을 하면서 동일한 로직을 반복하기 때문에 재귀를 이용하여 해결할 수 있다.

 

재귀 문제는 항상 base case 즉, 탈출 조건이 무엇인지를 확인해야 한다.

이 문제의 base case은 다음과 같다.

 

    1. 색종이의 크기가 1인 경우

       색종이의 크기가 1이면 더 이상 분할이 불가능하므로 재귀를 종료한다. 

    2. 색종이의 크기가 1보다 크지만, 모두 같은 색으로 이루어진 경우

       색종이가 모두 같은 색으로 이루어져 있으면 더 이상 색종이를 분할할 필요가 없다. 그 자체로

       흰색 색종이 혹은 파란 색종이 하나로 간주하기 때문이다. 그러므로 재귀를 종료한다.

 

색종이가 흰색과 파란색이 섞여 있으면 4등분으로 분할을 해야 한다.

색종이의 정보를 가장 왼쪽 위의 좌표(r, c)와 색종이 한 변의 길이(size)로 표현한다면,

이 색종이를 4분할로 분할하면 각각 4개의 분할된 색종이 정보는 아래와 같다.

 

가장 왼쪽 위 좌표 : (r, c) 한 변의 길이 : size/2

가장 왼쪽 위 좌표 : (r, c + size/2) 한 변의 길이 : size/2

가장 왼쪽 위 좌표 : (r + size/2, c) 한 변의 길이 : size/2

가장 왼쪽 위 좌표 : (r + size/2, c + size/2) 한 변의 길이 : size/2

 

총 4개로 분할되므로 재귀를 호출할 때 각 색종이 정보를 인자로 넣어주어서 총 4번 호출하면 된다.

반복문으로 재귀함수를 호출하는 부분은 다음과 같다.

	for (int i = r; i < r + size; i += size / 2) {
			for (int j = c; j < c + size; j += size / 2) {
				solve(i, j, size / 2);
			}
	}

 

소스코드 :