단지번호붙이기 풀이

문제 링크: https://www.acmicpc.net/problem/2667

백준 알고리즘 기초 2/2 600에서 5번째 - 2667번 단지번호붙이기를 풀어보았다.

 

풀이: https://ji-gwang.tistory.com/294 를 참고했다.

 

C++

 

Python

from collections import deque

def bfs(g,a,b):
	q=deque()
	q.append([a,b])
	g[a][b]=0
	cnt=1
	while q:
		x,y=q.popleft()
		g[x][y]=0
		for i in range(4):
			nx=x+dx[i]
			ny=y+dy[i]
			if nx<0 or nx>=len(g) or ny<0 or ny>=len(g):
				continue
			if g[nx][ny]==1:
				g[nx][ny]=0
				q.append([nx,ny])
				cnt+=1
	return cnt

n=int(input())
graph=[]
res=[]
for _ in range(n):
	graph.append(list(map(int,input())))
dx=[0,0,1,-1]
dy=[1,-1,0,0]
for i in range(n):
	for j in range(n):
		if graph[i][j]==1:
			cnt=bfs(graph,i,j)
			res.append(cnt)
res.sort()
print(len(res))
for i in res:
	print(i)

Java