[백준] 2667 단지번호붙이기

문제

• N크기의 정사각형 모양의 지도가 있고, 1은 집이 있는 곳을 0은 집이 없는 곳을 나타낸다.
• 집끼리 연결된 모임을 단지로 정의하고 단지에 번호를 붙이려고 한다.
• 각 단지에 속하는 집의 수를 오름차순으로 정렬해서 출력하기
• 5 <= N <= 25

 

풀이

• 단지 내 집들은 연결되어 있으므로 그래프 탐색을 통해 하나의 단지로 묶어준다.
• 한 번 방문한 집들을 -1 값으로 변경해 방문처리를 해준다.

 

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y, graph) :
    graph[x][y] = -1        # 현재 노드 방문처리
    q  = deque([(x, y)]) 
    cnt = 1                 # 단지 내 집 개수

    while q :
        x, y = q.popleft()
        # 상하좌우 확인
        for i in range(4) :
            nx, ny = x+dx[i], y+dy[i]

            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1 :
                q.append((nx, ny))
                graph[nx][ny] = -1
                cnt += 1
    return cnt

N = int(input())
graph = [list(map(int, input())) for _ in range(N)]

group = []
for i in range(N) :
    for j in range(N) :
        if graph[i][j] == 1 :
            group.append(bfs(i, j, graph))

print(len(group))   # 총 단지수
group.sort()
for i in range(len(group)) :
    print(group[i])

print(group)

 

References

• 백준 그래프 탐색