백준 2667

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

2667번: 단지번호붙이기

 

n= int(input())
graph = []
# 단지수
count = 0
# 각 단지의 가구수 담을 list
count_0 = []
# 2차원 list 입력받기 
# 행수 만큼 반복해 각행의 리스트를 담는다
for i in range(n):
    graph.append(list(map(int, input())))
# 현재위치부터 연결된 모든 노드를 방문하는 함수 만들기 
def dfs(x,y):
    #주어진 범위를 벗어나면 종료
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    #현재 위치가 집이면
    if graph[x][y] == 1:
        #현재 위치 방문했다함 
        graph[x][y] = 0
        # 방문처리 한다는게 집을 하나 셌다는 뜻
        global count
        count += 1
        # 기준 4방향으로 똑같이 탐색해줌
        # 주변이 길이거나 이미 센집이라면 각 함수는 False를 반환하고
        # 다 셌다는 뜻이기 때문에 True에 도착한다. 
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False
result = 0 
for i in range(n):
  for j in range(n):
    # 현재 위치에서 DFS 실행
    # 현재 위치에서 주변에 방문하지 않은 노드들 다 방문하고
    # True를 반환함 
    # 단지의 첫집을 만나면 그 단지를 탐색 다함
   if dfs(i,j) == True:
      result +=1
     # 하나의 단지를 다 셌기 때문에 
     # 그 동안의 카운트를 담아줌 한단지의 가정수
      count_0.append(count)
      count = 0
print(result)
# 각 단지의 집수를 오름차순으로 출력
# 문제를 똑바로 읽자 이거때문에 틀림
count_0.sort()
for i in count_0:
  print(i)