ProgrammingBeakjoonBFS

백준 2606 - 단지번호 붙이기 (Python)

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

링크

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

전체 소스 코드

def bfs(y, x):
    q = []
    q.append([y, x])
    check[y][x] = True
    count = 0

    while len(q) > 0:
        count += 1
        cntY = q[0][0]
        cntX = q[0][1]
        q.pop(0)

        for i in range(4):
            ny = cntY + dy[i]
            nx = cntX + dx[i]

            if 0 > ny or ny >= n or 0 > nx or nx >= n:
                continue

            if check[ny][nx] == False and field[ny][nx] != 0:
                check[ny][nx] = True
                q.append([ny, nx])

    values.append(count)


dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
n = int(input())
color = 0
values = []
check = [[False] * n for i in range(n)]
field = [[0] * n for i in range(n)]

for i in range(n):
    line = input()
    for j in range(len(line)):
        field[i][j] = int(line[j])

for i in range(n):
    for j in range(n):
        if check[i][j] == False and field[i][j] != 0:
            color += 1
            bfs(i, j)

values.sort()
print(color)
for i in values:
    print(i)
Share