[Swift] 백준 - 종이의 개수

문제

https://www.acmicpc.net/problem/1780

n*n 크기의 수를 입력받음 (n받고, n 만큼 한라인씩 입력받음)

각 칸에는 -1, 0 , 1 중 하나의 값을 입력받음

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이런 식으로 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성

접근 방법

음.. 1번 2번 로직대로 메소드를 짜고 while 돌리면 되지 않을까? 종이가 같거나 라인크기가 3일때 계산 후 나오고..

범위가 크기 때문에 dfs으로 해야할 것 같기도 하고..

dfs -> 시간초과 -> filter 대신 for문으로 중복제거 -> 겨우 통과..

해결

로직대로 짜줬다. 대신 종이를 자를경우 노드처럼 여러 경우의 수들이 생겨남으로 dfs로 접근해봤다. 근데 결국 나눠주는 과정을 했기 때문에 분할정복인가..?

처음 종이의 숫자가 같은지 여부를 체크해주는데, filter를 사용해주지 않고 for문을 돌려서 다를경우 바로 break로 나오는식으로 최대한 낭비를 하지않도록..? 작성했더니 시간이 조금 단축된 듯 하다..

그래서 현재 배열이 같은지 체크,

아니라면 라인의 크가기 3인지 -> 맞다면 for문 돌려서 각각 추가

이것도 아니라면 나눠주는 작업을 해주고 다시 재귀..

코드