단지번호붙이기

이전에 풀었던 미로탐색과 비슷하면서 조금 다른 문제였다.

1. for i in range(n):
   for j in range(n):
   if visited[i][j] == 0 and data[i][j] == 1:
   dfs(i, j)
   apt.append(result)
   result = 0
   모든 좌표를 다 확인하는데 그 중 방문을 안햇는데 1인곳을 탐색한다.

2. def dfs(a, b):
   global result
   result += 1
   visited[a][b] = 1
   for i in range(4):
   if n > a + dy[i] >= 0 and n > b + dx[i] >= 0:
   if visited[a + dy[i]][b + dx[i]] == 0 and data[a + dy[i]][b + dx[i]] == 1:

               visited[a + dy[i]][b + dx[i]] == 1
               dfs(a + dy[i], b + dx[i])
               

   dfs 에 들어가게 되면 전역변수 result를 불러 1을 더해준다. (if visited[i][j] == 0 and data[i][j] == 1: 이미 이 조건문을 통과했기 때문에)
   방문 처리 후 그 좌표에서 동서남북 확인해본다.
   만약 동서남북중 data가 1인데 방문을 안했으면 다시 dfs를 재귀적으로 불러준다
   그러면 또 result+=1로 한 그룹에 집이 몇개잇는지 셀수있다.

# https://www.acmicpc.net/problem/2667
n = int(input())
data = []

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

visited = [[0] * (n + 1) for i in range(n + 1)]

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def dfs(a, b):
    global result
    result += 1
    visited[a][b] = 1
    for i in range(4):
        if n > a + dy[i] >= 0 and n > b + dx[i] >= 0:
            if visited[a + dy[i]][b + dx[i]] == 0 and data[a + dy[i]][b + dx[i]] == 1:

                visited[a + dy[i]][b + dx[i]] == 1
                dfs(a + dy[i], b + dx[i])


result = 0
apt = []
for i in range(n):
    for j in range(n):
        if visited[i][j] == 0 and data[i][j] == 1:
            dfs(i, j)
            apt.append(result)
            result = 0

print(len(apt))
apt.sort()
for i in apt:
    print(i)