[백준(BOJ)] 2667번 단지번호붙이기

문제

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

2667번: 단지번호붙이기

지도를 보고 연결된 집의 모임을 단지로 정의하고, 각 단지에 번호를 붙여 총 단지수와 단지 내 집의 수를 출력하는 문제다.

예시

Example 1:

Input: 7
	0110100
	0110101
	1110101
	0000111
	0100000
	0111110
	0111000
Output: 3
	7
	8
	9

풀이

n = int(input())
# 지도
grid = []
for _ in range(n):
    grid.append(list(map(int, input().rstrip())))
# 상하좌우 이동을 위한 방향 설정
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 단지 내 집의 수
cnt = 0

def dfs(x, y):
    global cnt
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
  # 현재 위치가 집인 경우 cnt 증가하고 0으로 바꿔서 방문했음을 표시
    if grid[x][y] == 1:
        cnt += 1
        grid[x][y] = 0
	# 상하좌우 이동하며 dfs 수행
        for i in range(4):
            dfs(x + dx[i], y + dy[i])
        # 단지 내의 모든 집을 탐색한 경우 True 반환
        return True
  # 현재 위치가 집이 아닌 경우 False 반환
    return False

res = []

for i in range(n):
    for j in range(n):
    # 현재 위치가 집이면 dfs 수행하고 cnt를 결과 리스트에 추가
        if dfs(i, j):
            res.append(cnt)
            # cnt 초기화
            cnt = 0
res.sort()
print(len(res))
for r in res:
    print(r)