문제
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
아이디어
코드
python
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
graph = [] # 입력받을 그래프를 담을 리스트 선언
result = [] # 결과를 담을 리스트 선언
count = 0
for _ in range(N):
graph.append(list(map(int, input().rstrip())))
# 한 점을 기준으로 (위 아래 왼쪽 오른쪽) 으로 한칸 씩 이동할 좌표 설정
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def dfs(x, y):
global count
if x < 0 or x >= N or y < 0 or y >= N:
return
if graph[x][y] == 1:
count += 1
graph[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
dfs(nx, ny)
# 그래프의 원소가 1일때만 dfs로 집을 방문한다.
for i in range(N):
for j in range(N):
if graph[i][j] == 1:
dfs(i, j)
result.append(count)
count = 0
result.sort() # 오름차순으로 정렬
print(len(result)) # 총 단지수 출력
for k in result: # 각 단지마다 집의 수 출력
print(k)