[백준 2667] [dfs/bfs] 단지번호붙이기

💻 백준 2667번 [단지번호붙이기]

풀이)

n = int(input())
map_ = [list(map(int,input())) for _ in range(n)]

visited = [[0]*n for _ in range(n)]
cnt_lst = []
cnt = 0
def dfs(x,y) :
    global cnt 
    # 1. 방문한 노드인지 확인
    if not visited[x][y] :
        # 방문처리
        visited[x][y] = 1 
        if map_[x][y] == 0 : return # !!!!!!!!!!!!!!!!!!!!!!!!!!!이거 한줄 안해서 틀렸었음
        # 2. 인접노드 순회
        for [i,j] in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]] :
            if 0 <= i <= n-1 and 0 <= j <= n-1 : 
                if map_[i][j] == 1 and not visited[i][j]:
                    cnt += 1 
                    dfs(i,j)
                elif map_[i][j] == 0 :
                    visited[i][j] = 1 
    return

for i in range(n) :
    for j in range(n) :
        if not visited[i][j] : 
            if map_[i][j] == 1 : cnt = 1
            else : cnt = 0
            dfs(i,j)
            if cnt != 0 : cnt_lst.append(cnt)

print(len(cnt_lst))
print(*sorted(cnt_lst),sep='\n')

 

메모리	시간	언어	코드길이
29396KB	68ms	Python 3	919B