[DFS, BFS] 백준 2667번: 단지번호붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

섬을 세는 유명한 문제에 갯수까지 세는 것이 추가된 문제다.

DFS로 탐색하면서

미지의 단지를 발견할때 마다 island에 1을 더해주고 ( 단지 개수)

집을 발견할때마다 1을 더해주는 식으로 단지 내 집 개수를 구하였다.

n = int(input())

table = []
for i in range(n):
    table.append(list(input()))

island = 0
houses = []

def check(x,y):
    if 0 <= x < n and 0 <= y < n and table[x][y] == '1':
        table[x][y]='0'
        a = check(x-1,y)
        b = check(x+1,y)
        c = check(x,y-1)
        d = check(x,y+1)
        return 1+a+b+c+d
    else:
        return 0

for x in range(n):
    for y in range(n):
        if table[x][y] == '1':
            island +=1
            houses.append(check(x,y))

print(island)
for h in sorted(houses):
    print(h)