단지번호붙이기

풀이

 BFS, DFS 모두 가능한 문제다. 이중 for 문으로 리스트를 순회하면서 방문하지 않은 1을 만나면 BFS/DFS 호출해주면 된다. 그리고 BFS/DFS는 개수를 반환하면 된다. 시간복잡도는 이중 for 문을 통한 노드 탐색 O(N^2), 노드에 붙어있는 가능한 간선 탐색 O(N^2), 따라서 총 시간복잡도는 O(N^2)이다.

N = int(input())
graph = []
result = []
visited = [[False] * N for _ in range(N)]
for i in range(N):
    graph.append(list(map(int, input())))

# 동, 서, 남, 북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def dfs(x,y,c):
    graph[x][y] = 0
    visited[x][y] = True
    c += 1
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<= nx < N and 0<= ny < N:
            if graph[nx][ny] == 1 and not visited[nx][ny]:
                c = dfs(nx,ny,c)
    return c
for x in range(N):
    for y in range(N):
        if graph[x][y] != 0:
            count = dfs(x,y,0)
            result.append(count)

print(len(result))
result.sort()
for s in result:
    print(s)

시간복잡도 : O(N^2)