[백준] 2667번 단지번호붙이기 / 파이썬(python)

# 문제 링크

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

2667번: 단지번호붙이기

# Soultion

DFS를 이용하여 푼 문제이다.

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int,input())))
 
grp = []
cnt = 0
dx = [-1,1,0,0] # 상하좌우
dy = [0,0,-1,1]
 
def dfs(x,y):
    global cnt
    if x<0 or x>=n or y<0 or y>=n: # 범위
        return False
    
    if graph[x][y]==1:
        cnt +=1
        graph[x][y] = 0
        for i in range(4):
            dfs(x+dx[i],y+dy[i])
        return True
    
    
for i in range(n):
    for j in range(n):
        if dfs(i,j)==True:
            grp.append(cnt)
            cnt = 0
            
print(len(grp))
grp.sort()
for i in grp:
    print(i)

 

17. 단지의 집 개수를 구하기위해 카운팅을 해준다.

26. 한 개의 그룹이 완성되면 카운팅한 집의 개수를 리스트에 저장한 뒤, 0으로 초기화해준다.