문제이해
연결된 1의 덩어리 = 단지수 구하기
각 덩어리의 개수 = 집의 수 구하기
깊이 우선탐색(dfs)
1. 입력배열에서 1이고 방문배열이 0이면 거기서부터 단지수세어주고 dfs돌기
2. dfs돌면서 stack에 담아서 집의개수인 cnt 세어주기
3. 빈배열 lst 을 만들고 집의 개수=cnt담아서 오름차순정렬후 출력
실패코드
- apart배열에서 1인 수를 찾아 danji수를 셌는데 이러면 연결된 개수가 나오는게 아니라
그냥 apart배열에서 1의 총개수가 나옴 -> visited가 1인곳은 dangi수 세면 안됨X
N = int(input())
apart = [list(map(int,input())) for _ in range(N)]
visited = [[0]*N for _ in range(N)]
di = [-1,0,1,0]
dj = [0,1,0,-1]
# 깊이 우선 탐색(dfs) 사용해서 1이 연결된 개수 = 단지수 구하기 ,
# 각단지에서 1의 개수를 세서 lst에 담고 오름차순에서 순차적으로 출력
def dfs(x,y,apart,visited,N):
stack = [(x,y)]
cnt = 1
while stack:
(x,y) = stack[-1]
for d in range(4):
nx = x + di[d]
ny = y + dj[d]
if 0<=nx<N and 0<=ny<N and visited[nx][ny] == 0 and apart[nx][ny] == 1:
stack.append((nx,ny))
visited[nx][ny] = 1
cnt += 1
break
else:
stack.pop()
lst.append(cnt)
danji = 0
lst = []
for i in range(N):
for j in range(N):
if apart[i][j] == 1:
danji += 1
visited[i][j] = 1
dfs(i,j,apart,visited,N)
print(danji)
print(lst)
N = int(input())
apart = [list(map(int,input())) for _ in range(N)]
visited = [[0]*N for _ in range(N)]
di = [-1,0,1,0]
dj = [0,1,0,-1]
# 깊이 우선 탐색(dfs) 사용해서 1이 연결된 개수 = 단지수 구하기 ,
# 각단지에서 1의 개수를 세서 lst에 담고 오름차순에서 순차적으로 출력
def dfs(x,y,apart,visited,N):
stack = [(x,y)]
cnt = 1
while stack:
(x,y) = stack[-1]
for d in range(4):
nx = x + di[d]
ny = y + dj[d]
if 0<=nx<N and 0<=ny<N and visited[nx][ny] == 0 and apart[nx][ny] == 1:
stack.append((nx,ny))
visited[nx][ny] = 1
cnt += 1
break
else:
stack.pop()
lst.append(cnt)
danji = 0
lst = []
for i in range(N):
for j in range(N):
if apart[i][j] == 1 and visited[i][j] == 0:
danji += 1
visited[i][j] = 1
dfs(i,j,apart,visited,N)
print(danji)
lst.sort()
for i in lst:
print(i)
