백준_샤워실 바닥 타일 깔기 small & large(분할정복)

알고리즘 종류: 분할 정복
혼자서 풀었나요?: O

처음에는(정사각형 한 변의 길이가 최대 4일 때) 1. 배수구가 있는 사분면을 찾고 2. 해당 사분면은 배수구 위치를 제외한 모든 원소를 같은 숫자로 채운 다음에 3. 나머지 3개의 사분면은 모였을 때 가운데에 ㄱ자 모양 타월이 올 수 있도록 원소 하나를 제외한 나머지 원소를 같은 숫자로 채우고 4. 마지막에 가운데 ㄱ자 모양 타월을 다른 숫자로 채우려고 했었다

그런데 이렇게하면 3번부터 막힌다ㅎ 그래서 스터디장 님께서 주신 힌트를 보고 구현했다

문제 풀이

1 | 3

2 | 4

1. 정사각형을 4개의 사분면으로 나눈다 나는 위와 같이 나누었다
2. 배수구가 있는 사분면을 제외한 나머지 사분면의 가장 정중앙(사분면으로 나누지 않고 정사각형 자체를 보았을 때)가 ㄱ자 타일이 되도록 채운다 이건 사분면을 나눴을 때 사용했던 변수 m을 써서 구현 가능하다
3. 재귀로 들어가면서 반북. 배수구를 포함한 사분면과 더불어 나머지 3개의 사분면 모두 함수로 호출한다
   Base case: n=1일 때 즉 정사각형 한 변의 길이가 2일 때 배수구를 빼고 전부 같은 숫자로 채워준다

여기서 중요한 점은 2에서 다시 1로 재귀를 반복할 때, 배수구 위치를 넣어주어야 하는데 2에서 칠한 부분은 원래 정한 배수구가 아니더라도 각 사분면 안으로 재귀를 들어갈 때 배수구 취급을 해 주어야 한다는 것이다. 함수롤 또 호출할 때도 그 함수에 베수구 x, y좌표 인자에 그 색칠한 부분 원소의 x, y좌표를 넣어준다. 배수구가 있는 사분면은 그대로 그 인자에 계속 배수구 x, y 좌표를 넣어주면 된다

코드는.. 내가 너무 더럽게 짜서ㅠㅠ 생락한다... 조만간 깔끔하게 수정해서 올려야지..........