# 2667: 단지 번호 붙이기

n = int(input()) # 지도의 크기 
graph = []

for i in range(n):
  graph.append ( list(map(int,input())))

def dfs(x,y,num):

  if x <0 or y<0 or x>=n or y>=n : 
    return False 
  
  if graph[x][y] == 1 : 

    graph[x][y] = num+1

    dfs(x-1,y,num)
    dfs(x+1,y,num)
    dfs(x,y-1,num)
    dfs(x,y+1,num)

    return True 
  return False 

num = 1 
for x in range(n):
  for y in range(n):
    if dfs(x,y,num) == True:
      num += 1 

cnt_num = [0] * (num+1)

for x in range(n):
  for y in range(n): 
    if graph[x][y] != 0 :
      cnt_num[ graph[x][y] ] += 1 

total_num = cnt_num[2:num+1]
total_num.sort()

cnt  = len(total_num)
print(cnt)
for i in range(cnt):
  print(total_num[i])

 

참고 ) 음료수 얼려 먹기 문제 bright-code.tistory.com/78?category=423266

 

1. 풀이 방법 : dfs 이용 

2. 코드 설명 

 

dfs 를 사용하여 푼다. 

1 이면 집을 의미한다. 문제에서는 단지 번호를 1 부터 붙였지만, dfs 처리가 어려워서 나는 2 부터 붙였다. 

한 번 dfs  함수를 돌 때, 나와 붙어 있는 것들은 모두 num+1 로 바꿔 준다. 

 

나중에 숫자 별로 집의 수를 세어서 cnt_num 리스트에 넣어 주었고, 

위 코드에서는 0, 1 의 단지에 속한 집이 없으므로 필요한 부분만 넣은 리스트인 total_num 을 선언해 주었다. 

오름차순으로 sort 하고 길이와 값을 출력한다. 

 

 

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기