단지번호붙이기

2667번: 단지번호붙이기

 

나의 풀이

from collections import deque
import sys
input = sys.stdin.readline

n_ct = int(input())
map_list = []
for _ in range(n_ct):
    map_list.append(list(map(int, input().rstrip())))

r_ct = 0
r_list = []

for i in range(n_ct):
    for j in range(n_ct):
        if map_list[i][j] == 1:
            r_ct += 1
            now_r_ct = 0
            queue = deque([(i,j)])
            while queue:
                a,b = queue.popleft()
                now_r_ct += 1
                map_list[a][b] = 0
                for m_a, m_b in ((1,0),(-1,0),(0,1),(0,-1)):
                    new_a, new_b = a+m_a, b+m_b
                    
                    if (0 <= new_a < n_ct) and (0 <= new_b < n_ct) and (map_list[new_a][new_b] == 1)  and ((new_a, new_b) not in queue):
                        queue.append((new_a, new_b))
            r_list.append(now_r_ct)
print(r_ct)
r_list.sort()
for i in r_list:
    print(i)

 

시간 복잡도

for i in range(n_ct) : 모든 경로를 탐색하여 단지를 확인하므로 ( 이차형 시간 복잡도 )
    for j in range(n_ct) :
해당 알고리즘 시간 복잡도는 : 이차형 시간 복잡도 ( O(n**2) )