[www.acmicpc.net/problem/2667]
#풀이
- dfs,bfs를 사용해서 단지 크기를 측정한다.
1. 이차원 배열안에 1이 있으면 1이 있는 위치 부터 bfs,dfs를 사용한다.
2. 단지갯수와 정렬한 단지 크기를 출력한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | import sys input = lambda: sys.stdin.readline().rstrip() #sys.stdin = open('input.txt', 'r') def dfs(i,j): stack=[(i,j)] data[i][j]=0 count=1 while stack: a,b=stack.pop() for k in range(4): da=a+dx[k] db=b+dy[k] #da,db가 data 범위 안에 있고 data[da][db]를 방문 하지 않았을 때 if 0<=da<n and 0<=db<n and data[da][db]: data[da][db]=0 stack.append((da,db)) count+=1 result.append(count) #상하좌우 dx=[0,0,1,-1] dy=[1,-1,0,0] n=int(input()) data=[[int(i) for i in input()] for _ in range(n)] result=[] #모든 경우 탐색 for i in range(n): for j in range(n): if data[i][j]: dfs(i,j) print(len(result)) for i in sorted(result): print(i) | cs |
댓글 쓰기