[백준/dfs] 2667번: 단지번호 붙이기

-문제: https://www.acmicpc.net/problem/2667

-풀이 이해:

dfs가 생각이 나서 dfs로 풀려고 했는데, 전체 갯수는 세는 건 알고 있는데 

각 단지에 해당하는 단지수를 어떻게 풀어야할지 몰랐다. 

dfs에서 True,False 반환하는 거 말고, 1을 만날때마다 cnt를 세고 싶은데 어떻게 해야할지 몰랐다.

찾아보니 global 키워드를 이용하면 된다는 걸 알았다 

 

-정답풀이:

단지가 완성이 되면, cnt값을 리스트에 삽입하고 다시 cnt를 0으로 초기화한다

n=int(input())
s=[]

for _ in range(n):
    s.append(list(map(int,input())))
    
def dfs(x,y):
    if x<0 or y<0 or x>=n or y>=n:
        return False
    if s[x][y]==1:
        global cnt 
        s[x][y]=0
        cnt+=1
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False

result=0
cnt=0
apartment=[]
for i in range(n):
    for j in range(n):
        if dfs(i,j)==True:
            apartment.append(cnt)
            result+=1
            cnt=0          
print(result)
apartment.sort()  
for i in range(result):
    print(apartment[i])