BOJ 2667 - 단지번호 붙이기

folder_open Algorithm / BOJ / silver | date_range 12 Mar 2025

sell #BOJ #2667 #silver #python #파이썬 #코딩테스트 #알고리즘

맨 위로

• 문제 링크
• 구현
• 코드

문제 링크

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

구현

단순한 BFS, DFS 문제이다. 방문하지 않은 첫 노드를 들어갈 때 총 단지 수를 +1 하고, 단지 내 집 수를 보관하는 배열을 하나 만들어 카운트한 집 수를 추가해준다.

코드

from sys import stdin
from collections import deque
input = lambda : stdin.readline()

n = int(input())
rec = []
for _ in range(n):
    rec.append(list(map(int," ".join(input()).split())))
visited = set()
counter = []
house = 0
chk = [[1, 0, -1, 0], [0, 1, 0, -1]]
for i in range(n):
    for j in range(n):
        if rec[i][j] and (i, j) not in visited:
            house += 1
            visited.add((i, j))
            queue = deque()
            queue.append((i, j))
            count = 1
            while queue:
                node = queue.popleft()
                for row, col in zip(chk[0], chk[1]):
                    new_y, new_x = node[0] + row, node[1] + col
                    if 0 <= new_x < n and 0 <= new_y < n:
                        if rec[new_y][new_x] and (new_y, new_x) not in visited:
                            queue.append((new_y, new_x))
                            visited.add((new_y, new_x))
                            count += 1
            counter.append(count)
print(house)
for i in sorted(counter):
    print(i)