[BaekJoon Online Judge] 2667 – 단지번호붙이기

문제

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

소스코드

지도 내의 모든 좌표를 탐색하여, 집이 발견될 때마다 그 집의 좌표부터 dfs를 이용해 연결된 집을 모두 찾는다. 계속해서 앞의 과정을 반복하는데 단지 번호만 하나씩 늘려주기만 하면 해결할 수 있다.

dx=[0,1,0,-1]
dy=[1,0,-1,0]
N = int(input())
town = [list(map(int,list(input()))) for _ in range(N)]
district = 1
cnts,stack = [],[]
done = False
while done == False:
    for i in range(N*N):
        if town[i//N][i%N] == 1:
            stack.append((i//N,i%N))
            district += 1
            town[i//N][i%N] = district
            cnts.append(1)
            break
        if i == N*N-1:
            done = True
    while stack:
        x,y = stack.pop(-1)
        for i in range(4):
            to_x,to_y = x+dx[i],y+dy[i]
            if to_x>=0 and to_y>=0 and to_x<N and to_y<N:
                if town[to_x][to_y] == 1:
                    stack.append((to_x,to_y))
                    town[to_x][to_y] = district
                    cnts[len(cnts)-1] += 1
cnts.sort()
print(len(cnts))
for i in range(len(cnts)):
    print(cnts[i])