728x90
그래프 탐색 문제로 DFS, BFS 둘다 사용하여 풀이가 가능하다.
아래는 DFS를 활용한 풀이이다.
DFS
n = int(input()) # 정사각형 모양의 지도의 크기 입력
# 지도 입력 받기
map_data = [list(map(int, input())) for _ in range(n)]
visited = [[False] * n for _ in range(n)] # 방문 여부를 저장하는 배열 초기화
def dfs(x, y):
visited[x][y] = True # 현재 위치를 방문했음을 표시
count = 1 # 단지의 크기를 세기 위한 변수 초기화
for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]: # 현재 위치에서 이동할 수 있는 방향에 대해 반복
nx, ny = x + dx, y + dy # 다음 이동할 위치 계산
if 0 <= nx < n and 0 <= ny < n and map_data[nx][ny] == 1 and visited[nx][ny] == False: # 다음 위치가 유효하고, 집이 있는 곳이며 아직 방문하지 않았다면
count += dfs(nx, ny) # 해당 위치로 이동하여 재귀적으로 탐색
return count # 단지의 크기 반환
total = [] # 각 단지의 크기를 저장할 리스트 초기화
for i in range(n): # 모든 위치에 대해 반복
for j in range(n):
if map_data[i][j] == 1 and visited[i][j] == False: # 집이 있는 곳이고 아직 방문하지 않았다면
count = dfs(i, j) # 해당 위치에서 단지의 크기를 구함
total.append(count) # 단지의 크기를 리스트에 추가
print(len(total)) # 총 단지의 수 출력
for c in sorted(total): # 단지의 크기를 오름차순으로 정렬하여 출력
print(c)
728x90
