2667번: 단지번호붙이기

Problem Link
https://www.acmicpc.net/problem/2667

✅ Problem Summary

주어진 행렬에서 수평(horizontally), 수직(vertically)으로 이어진 구역(1로 표시, 문제에서는 단지로 표현)들의 크기(문제에서는 집의 갯수로 표현)를 구하는 문제

• 출력 형태
  : 첫 번째 줄에는 총 단지 수, 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력

이미지 출처: 백준 2667번

---

🧮 Applied Theory & Algorithm

1. 깊이 우선 탐색(Depth-First Search)

그림출처:Wikipedia

---

📑 My Answer

• 메모리 : 31084KB
• 시간 : 68ms

def dfs(matrix, n, pos, cnt):
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    matrix[pos[0]][pos[1]] = '0'
    for i in range(4):
        ni, nj = pos[0]+dx[i], pos[1]+dy[i]
        if 0<=ni<n and 0<=nj<n and matrix[ni][nj] == '1':
            cnt = dfs(matrix, n, pos=(ni, nj), cnt=cnt+1)
    return cnt
    
def main():
    n = int(input())
    matrix = []
    for _ in range(n):
        matrix.append(list(input()))
    result = []
    for i in range(n):
        for j in range(n):
            if matrix[i][j] == '1':
                cnt = dfs(matrix, n, pos=(i,j), cnt=1)
                result.append(cnt)
    result.sort()
    print(len(result))
    print(*result, sep='\n')

main()

---