반응형
dfs 방식을 이용해 문제에 접근했고
번지 수를 구분하기 위해서
어떤 한 번지 내를 탐색할 때 번지 내에 있는 단지 수를 세면서 동시에 번지의 값을 다 0으로 바꿔서 다음 번지를 찾을 수 있도록 했다.
import sys
input = sys.stdin.readline
n = int(input())
mat = [list(input()) for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
res=[]
for i in range(n):
for j in range(n):
if mat[i][j]=='1':
stack=[[i,j]]
visited=[]
cnt=0
while stack:
item = stack.pop()
if item not in visited:
visited.append(item)
a,b=item[0],item[1]
mat[a][b]=0
cnt+=1
for k in range(4):
x = a+dx[k]
y = b+dy[k]
if 0<=x<n and 0<=y<n and mat[x][y]=='1':
stack.append([x,y])
res.append(cnt)
res.sort()
print(len(res))
for num in res:
print(num)
반응형
'Algorithm > Baekjoon' 카테고리의 다른 글
2644번 파이썬 (0) | 2022.03.20 |
---|---|
10844번 파이썬 (0) | 2022.03.17 |
2606번 파이썬 (0) | 2022.03.16 |
2178번 파이썬 (0) | 2022.03.16 |
1260번 파이썬 (0) | 2022.03.16 |