이전에 풀었던 그래프 문제보다 업그레이드 된 문제입니다.
이전 문제가 단순히 하나의 노드에서 몇 개의 노드로 뻗어나가냐의 수준이었다면,
이번에는 총 단지와 각각 단지마다 집의 수를 구해야 하는 문제였습니다.
일단, 집이 있는 경우 1이고, 없는 경우가 0이므로 main 함수 부분에서 2중 for문을 돌며
arr[i][j] 가 1인 경우에 DFS 함수를 실행해 줍니다. 동시에 단지 수를 세는 total 변수에 1을 추가해 줍니다.
DFS 함수 안에선 global화 된 ct 변수를 1 증가시켜 줍니다.
또한 해당 인덱스를 0으로 바꿔주고, nx, ny라는 리스트를 활용하여 남,서,북,동의 좌표를 얻은 뒤,
그 좌표가 0 보다 작거나, 입력받은 N보다 크거나 같으면 범위에 벗어나므로 continue를 해 줍니다.
그렇지 않은 경우엔 해당 좌표의 값이 1인 경우에만 DFS 함수를 가동시켜 줍니다.
주변 모든 1을 탐색한 후, 메인으로 돌아와 ct는 answer이라는 리스트에 append되고, 다시 0으로 초기화 됩니다.
(즉, 1번 단지 탐색이 끝났고, 다음 단지를 탐색하러 간다고 생각하시면 됩니다.)
큰 그림에서 설명 드리자면, 먼저 바깥에서 2중 for문으로 인덱스의 값이 1인 지점을 먼저 찾습니다.
1인 지점에서 DFS 함수를 들어가고, total 함수를 증가시켜 줍니다.
DFS 함수를 돌며 주변 1을 다 0으로 바꿔주고, ct 변수를 1씩 더해서 단지의 집의 수를 셉니다.
바깥 2중 for문 기준으로, 해당 인덱스 값이 1인 지점에서 DFS 함수가 실행되고 나면, 해당 단지의 값들이 모두 0으로 되어 있게 됩니다.
def DFS(x, y):
global ct
arr[x][y] = 0 # 현재 해당 인덱스를 0으로 만들어 줍니다.
ct += 1 # 인덱스가 1인 경우, ct 변수를 1 증가시켜줍니다.
for i in range(4):
dx = x + nx[i]
dy = y + ny[i]
if dx < 0 or dx >= N or dy < 0 or dy >= N: # 현재 인덱스 기준으로 아래,왼쪽,위,오른쪽을 보며, 범위에 벗어나면 continue로 지나칩니다.
continue
if arr[dx][dy] == 1: # 만약, 아래,왼쪽,위,오른쪽 인덱스 중 1이 있으면, 해당 인덱스로 가서 DFS 함수를 실행합니다.
DFS(dx, dy)
N = int(input())
ct = 0
arr = []
answer = []
total = 0
nx = [-1, 0, 1, 0] # nx, ny는 주변 4방향 인덱스를 반복문으로 돌기 위해 만든 리스트입니다.
ny = [0, -1, 0, 1]
for i in range(N):
arr.append(list(map(int, input())))
for i in range(N):
for j in range(N):
if arr[i][j] == 1: # 인덱스가 1인 경우만 DFS 함수로 들어갑니다.
DFS(i, j) # 이 부분에서, DFS함수가 주변 1을 돌며 0으로 바꿔줍니다.
total += 1 # 총 단지의 수를 증가시켜 줍니다.
answer.append(ct) # 집의 수를 answer에 append 해주고, ct를 0으로 초기화해줍니다.
ct = 0
answer.sort() # 오름차순으로 출력하라고 했기에 sort 함수를 사용하였습니다.
print(total)
for i in answer:
print(i)