[Python] 2667: 단지번호붙이기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import sys
from collections import deque
 
 
def find_node(y, x):
    array = []
    dy = [0011]
    dx = [1100]
 
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
 
        if 0 <= nx < n and 0 <= ny < n:
            if graph[ny][nx] == 1:
                array.append((ny, nx))
 
    return array
 
 
def bfs(start):
    queue = deque([start])
    graph[start[0]][start[1]] = 2
    total = 0
    while queue:
        v = queue.popleft()
        total += 1
        arr = find_node(v[0], v[1])
        for i in arr:
            queue.append(i)
            graph[i[0]][i[1]] = 2
    if total > 0:
        num.append(total)
 
 
= int(sys.stdin.readline().strip())
 
graph = []
num = []
 
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().strip())))
 
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            bfs((i, j))
 
num.sort()
 
print(len(num))
for i in num:
    print(i)
 
 
cs

관련글

제목 작성자 작성일