백준 2667번 : 단지번호 붙이기 with 파이썬

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

2667번: 단지번호붙이기

 

<DFS : 스택, 재귀함수>

 

DFS는 연결된 v를 찾아 끝까지 파고드는 구조기 때문에 재귀함수를 사용하여 구현하는 경우가 많다.

 

재귀함수의 경우

1. stack over flow가 되지 않도록 끝나는 조건을 명확히 제시해야 하고

2. 함수의 return으로 값을 받아오는 bfs와 달리 전역변수를 활용해 업데이트 한다.

 

import sys
input=sys.stdin.readline

n=int(input())
g=[list(map(int, input().strip())) for _ in range(n)]
chk=[[False]*n for _ in range(n)]
each=0
result=[]

dy=[0,1,0,-1]
dx=[1,0,-1,0]
def dfs(y,x):
    global each
    each+=1
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<n and 0<=nx<n :
            if g[ny][nx]==1 and chk[ny][nx]==False:
                chk[ny][nx]=True
                dfs(ny, nx)


for j in range(n):
    for i in range(n):
        if g[j][i]==1 and chk[j][i]==False :
            chk[j][i]=True
            each=0
            dfs(j,i)
            result.append(each)  

result.sort()
print(len(result)) # 그림의 총 갯수

for i in result:
    print(i)       # 그림의 구성 요소의 갯수