1. 문제

---

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

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

2. 아이디어

---

• 연결되어 있는 1을 찾기

  • 2차원 그림에서 붙어있는 1을 연결되어 있는 그래프로 생각하기
  • DFS로 연결된 덩어리 카운트
  • 노드를 방문할 때마다 count를 해줘서 덩어리 안에 있는 집을 카운트
  • 덩어리, 집 개수 출력

3. 코드

---

mine

# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x,y):
  global count
  # 주어진 범위를 벗어나는 경우 즉시 종료
  if x <= -1 or x >= n or y <= -1 or y >= n:
    return False
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == 1:
    # 해당 노드 방문 처리와 함께 카운트
    graph[x][y] = 0
    count += 1
    # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
    dfs(x-1, y)
    dfs(x, y-1)
    dfs(x+1, y)
    dfs(x, y+1)
    return True
  return False

# 정사각형 n x n
n = int(input())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
  graph.append(list(map(int, input())))

# 모든 노드(위치)에 대하여 1의 집합 확인
lump = 0 # 덩어리 수
count = 0 # 덩어리 안에 몇 개의 집이 있는지
house = [] # count 모아놓은 리스트

for i in range(n):
  for j in range(n):
    # 현재 위치에서 DFS 수행
    if dfs(i, j) == True:
      lump += 1
      house.append(count)
      count = 0

print(lump)
for houseNumber in sorted(house):
  print(houseNumber)

DFS 개념 설명 및 기본 코드 출처 : https://www.youtube.com/watch?v=PqzyFDUnbrY