Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 2667 단지번호붙이기
백준 2667 단지번호붙이기
문제
정사각형 모양의 지도가 있다. 1은 집이 있는 곳, 0은 집이 없는 곳을 나타낸다.
철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고 단지에 번호를 붙이려 한다.
여기서 연결되었다는 것은 어떤 집이 좌우, 위아래로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다.
지도를 입력하여 단지 수를 출력하고 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
- 첫째줄: 지도의 크기 N
- 두번재줄 ~: 지도
출력
첫번째 줄: 총 단지수 2번째 줄~: 각 단지내 집의 수를 오름차 순으로 정렬하여 한 줄에 하나씩 출력
해결 방식
bfs 알고리즘으로 풀었다.
- 1로 표시된 노드 방문한다.
- 다음 노드를 찾는다.
- 다음 노드가 결정되면 이후 해당 노드를 재방문 하지 않기위해 값을 0으로 변경하고 count를 1 증기시킨다.
코드
from collections import deque
n = int(input())
graph = [list(map(int, input())) for _ in range(n)]
def bfs(x, y):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
queue.append((x, y))
graph[x][y] = 0
count = 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= n:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = 0
queue.append((nx, ny))
count += 1
return count
count = []
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
count.append(bfs(i, j))
count.sort()
print(len(count))
for complex in count:
print(complex)
