2667번 - 단지번호붙이기(Python)

풀이

bfs 혹은 dfs를 이용하여 집을 발견하면, 탐색이 끝날 때까지 이동 가능한 집의 개수를 센다.(아래 코드는 dfs)

 

코드

N = int(input())
board = [input() for _ in range(N)]

ans = []
visited = [[False for _ in range(N)] for _ in range(N)]
dy = [0, 0, -1, 1]
dx = [-1, 1, 0, 0]

for i in range(N):
    for j in range(N):
        if not visited[i][j] and board[i][j] == '1':
            stack = [[i, j]]
            cnt = 1
            visited[i][j] = True
            while stack:
                node = stack.pop()
                y, x = node[0], node[1]
                for k in range(4):
                    ny = y + dy[k]
                    nx = x + dx[k]
                    if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and board[ny][nx] == '1':
                        cnt += 1
                        visited[ny][nx] = True
                        stack.append([ny, nx])
            ans.append(cnt)

ans.sort()
print(len(ans))
for a in ans:
    print(a)