[2667. 단지번호 붙이기]

코테 준비하다 보면 피할 수 없는 DFS 다루기.
BFS도 공부해야 하지만 일단 그래도 그나마 만만해보이는 DFS 부터 들들이 파보도록 하겠다 이마리야😁

재귀라는 개사기 툴을 사용하는게 멋져보여서 DFS에 꽂혔다

처음에는 치팅을 안하고 풀어보려 했는데.... 킁... 실패! (빡머갈 인증도장 쾅 👌)
https://www.acmicpc.net/problem/2667

## 입력 다루기 
n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int,input())))

위 코드는 기껏해야 입력만 재구성하는 거니까 이지피지~ 이건 마스터했다고 볼 수 있음 ㅎㅋ

dx = [0,0,1,-1]
dy = [1,-1,0,0]

위 코드는 4방향 탐색에 흔히 쓰이는 논리다 동서남북을 그래프에서 표현해야 할 때 거의 99프로 쓰이는 듯 ㅎㅋ

def dfs(x,y):
    if x<0 or x>=n or y<0 or y>=n: # 경계 침범 조건
        return False
    if graph[x][y] == 1: # 카운팅 할 집 발견했다면,
        graph[x][y] = 0 # 검사 완료 한 집은 0으로 바꾸고,
        global count
        count += 1 # 한 단지 안에 집 몇개인지 업데이트
        for i in range(4): # 사방 검사 후
            newx = x + dx[i]
            newy = y + dy[i]
            dfs(newx,newy)
        return True # 얘의 indent가 매우 중요
    elif graph[x][y] == 0:
        return False # 탐색 종료

위 코드가 이 문제 풀이의 본체다. 재귀를 잘 설계해놓으면 고생할 일이 없다
하지만 숨은 반례들이 불쑥 튀어나와서 개빡치긴 하는데... 실력이 늘면 커버 되겠지 뭐 ㅎㅋ

한가지 얻어갈 것은 return True / return False 에 관한 논리. 꼭 재귀에서 값을 output으로 다루지 않아도 된다는 것

jip = [] # 단지 카운팅
count = 0

for j in range(n):
    for k in range(n):
        if dfs(j,k) == True:
            jip.append(count)
            count = 0 # 다음 단지 카운팅을 위해 0

jip.sort()
print(len(jip))
for l in range(len(jip)):
    print(jip[l])

위 코드는 재귀를 다루어서 이제 답을 추출하는 과정인데,
단지찾기 문제의 특성상 모든 점들을 다 훑어가야한다는게 굉장히 킹받았다. 변칙. 앁~