[문제 풀이 20] 코드 트리 - 연결된 칸 찾기

연결된 칸 찾기

 

• 문제 유형 : DFS
• 사용언어 : Python
• 난이도 : 실버 1
• 출처 : 코드 트리

 

def dfs(grid, visited, x, y, n):
    stack = [(x, y)]
    size = 0  # 연결된 1의 개수를 세는 변수

    while stack:
        cx, cy = stack.pop()
        if visited[cx][cy]:
            continue
        visited[cx][cy] = True
        size += 1
        
        # 상, 하, 좌, 우 네 방향으로 이동 가능
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] == 1:
                stack.append((nx, ny))

    return size

n = int(input())
grid = []
for i in range(n):
    grid.append(list(map(int, input().split())))

visited = [[False] * n for _ in range(n)]
sizes = []  # 각 연결 구역의 크기를 저장할 리스트

for i in range(n):
    for j in range(n):
        if grid[i][j] == 1 and not visited[i][j]:
            size = dfs(grid, visited, i, j, n)
            sizes.append(size)  # 연결된 구역의 크기를 리스트에 추가

print(len(sizes))  # 연결된 구역의 총 수
for size in sorted(sizes):  # 연결된 구역의 크기를 오름차순으로 출력
    print(size)