[Softeer] 장애물 인식 프로그램 파이썬

* DFS 깊이 우선 탐색을 이용하는 문제

* 문제 조건 : 블록은 좌우 , 위아래 로만 연결 가능

* 상하좌우를 파악한 후 주변 값이 1이면 방문. 

* 한번 방문한 곳은 방문하지 않음

* 방문하지 않은 지점을 카운트

 

import sys

#---- DFS ----#
def dfs(x, y, graph, visited):
    if x < 0 or x >= len(graph) or y < 0 or y >= len(graph[0]):
        return 0
    if graph[x][y] == 0 or visited[x][y]:
        return 0
    visited[x][y] = True
    size = 1
    size += dfs(x - 1, y, graph, visited)
    size += dfs(x, y - 1, graph, visited)
    size += dfs(x + 1, y, graph, visited)
    size += dfs(x, y + 1, graph, visited)
    return size

n = int(input()) # map size
graph = [] # 2D binary matrix representing the map

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

visited = [[False] * n for _ in range(n)] # 2D matrix to track visited nodes
sizes = [] # list of sizes of each connected component

#---- number of block ----#
for i in range(n):
    for j in range(n):
        size = dfs(i, j, graph, visited)
        if size > 0:
            sizes.append(size)
print(len(sizes))

#---- number of 1 ----#
sizes.sort()
for size in sizes:
    print(size)