백준_2667_단지번호 붙이기_dfs_bfs_파이썬

문제 링크

2667번: 단지번호붙이기

 

size = int(input())
map1 = []
visited_map = [[False for _ in range(size)] for _ in range(size)]
for i in range(size):
    map1.append(list(map(int,list(input()))))
 
row_x = [1,-1,0,0]
col_y = [0,0,1,-1]
 
def dfs(row, col):
    global now_score
    if visited_map[row][col] == False and map1[row][col] == 1:
        now_score +=1
        visited_map[row][col] = True
        for i in range(4):
            now_x = row+row_x[i]
            now_y = col+col_y[i]
            if -1<now_x and now_x<size and -1<now_y and now_y<size:
                dfs(now_x,now_y)
    return now_score
 
def bfs(row,col):
    now_score = 0
    check_list = []
    if visited_map[row][col] == False and map1[row][col] == 1:
        visited_map[row][col] = True
        now_score += 1 
        check_list.append((row,col))
    while len(check_list)!=0:
        row,col = check_list.pop(0)
        for i in range(4):
            now_x = row+row_x[i]
            now_y = col+col_y[i]
            if -1<now_x and now_x<size and -1<now_y and now_y<size:
                if visited_map[now_x][now_y] == False and map1[now_x][now_y] == 1:
                    visited_map[now_x][now_y] = True
                    check_list.append((now_x,now_y))
                    now_score+=1
    return now_score
 
visited_map = [[False for _ in range(size)] for _ in range(size)]
 
score = []
now_score = 0
 
for i in range(size):
    for k in range(size):
        now_score = 0
        now_score = bfs(i,k)
        if now_score != 0:
            score.append(now_score)
score.sort()
print(len(score))
for i in score:
    print(i)