첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고,
그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
1
2
| N = int(input())
apt = [list(int(c) for c in input()) for _ in range(N)]
|
DFS
- 배열의 요소를 하나씩 방문하면서, 1일 경우 위/아래/왼/오가 1인지 체크하고,
- 1일 경우, 방문했던 곳이 아니라면 동일한 방법으로 체크한다.
1
2
3
| visited = [[False]*N for _ in range(N)]
dir = [[0,1], [0,-1], [1,0], [-1,0]]
|
1
2
3
4
5
| for i in range(N):
for j in range(N):
if apt[i][j] == 1 and not visited[i][j]:
count = 0
dfs(i, j)
|
1
2
3
4
5
6
7
| for d in dir:
y = dy + d[0]
x = dx + d[1]
if 0 <= y < N and 0 <= x < N:
if apt[y][x] and not visited[y][x]:
dfs(y, x)
|
- 이 때, 단지별 아파트 개수를 출력하기 위해
count+1 을 수행한다.
1
2
3
4
| def dfs(dy, dx):
visited[dy][dx] = True
global count
count += 1
|
apt[i][j] == 0 or visited[i][j] == True 이면 더 이상 dfs 를 호출하지 않고, 이는 즉 단지가 구성되었음을 의미- 다음 단지로 넘어가기 전
sort 를 사용하기 위해 list에 count를 append한다.
1
2
3
4
| if apt[i][j] == 1 and not visited[i][j]:
count = 0
dfs(i, j)
countList.append(count)
|
Output
첫 번째 줄에는 총 단지수를 출력하시오.
그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
1
2
3
4
| countList.sort()
print(len(countList))
for num in countList:
print(num)
|