[Graph] 단지번호 붙이기

박고은·2023년 5월 24일
0

알고리즘

목록 보기
12/12

from collections import deque

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

direction = {0: (0, 1), 1: (0, -1), 2: (1, 0), 3: (-1, 0)}

def BFS(neighbor, x, y):
    cnt = 1
    neighbor[x][y] = 0

    q = deque()
    q.append((x, y))

    while q:
        x, y = q.popleft()
        for i in range(4):
            x2, y2 = x+direction[i][0], y+direction[i][1]
            if 0<=x2<N and 0<=y2<N and neighbor[x2][y2]==1:
                cnt += 1
                q.append((x2, y2))
                neighbor[x2][y2] = 0

    return cnt

count = [BFS(neighbor, i, j) for i in range(N) for j in range(N) if neighbor[i][j]==1]

print(len(count))
for c in sorted(count): print(c)

주어진 단지 내 집의 위치 2차원 배열으로 표현
인접한 집들을 하나의 단지로 묶는 문제 -> BFS
이중 for 루프를 돌면서 값이 1인 경우에 BFS 함수를 실행
실행하면서 반환된 cnt를 배열로 생성

0개의 댓글