백준.단지번호붙이기.2667.py

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

2667번: 단지번호붙이기

import sys
def solution(house_adr_dic):
    def adj_add(house_add): # return adj adr list
        x,y = house_add
        return [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
    
    def dfs_set(node_dic): # dfs 알고리즘
        tm_keys, adj_adr_list_set = set(node_dic.keys()), []
        
        while tm_keys:
            visted_set, vist_stack = set(), []
            vist_stack.append(tm_keys.pop()) # 주소 중 하나를 start로
            while vist_stack:
                now_adr = vist_stack.pop()
                if now_adr not in visted_set: # 집합 탐색=> O(1)
                    visted_set.add(now_adr)
                    tm_keys.discard(now_adr) #remove 할때 없어도 오류 안나는거 까먹음
                    vist_stack.extend(node_dic[now_adr]) # 인접 주소 저장
            adj_adr_list_set.append(len(visted_set))
        return adj_adr_list_set

    house_adj_adr_dic = dict() # key = 집 주소, value = 인근 집 주소 list
    for house_adr in house_adr_dic:
        adj_list = adj_add(house_adr)
        tm_adr_list = []
        for i in range(4): # 인접한 house add list를 만드는 과정
            if house_adr_dic.get(adj_list[i],False): tm_adr_list.append(adj_list[i]) # house adr value is T or F
        house_adj_adr_dic[house_adr] = tm_adr_list

    return dfs_set(house_adj_adr_dic) # 연결된 집 개수 들의 리스트를 반환

if __name__ == '__main__':
    house_adr_dic = dict()
    n = int(sys.stdin.readline().rstrip())
    for y in range(n):
        tm_string = sys.stdin.readline().rstrip()
        for x,h in enumerate(tm_string):
            if h == '1':
                house_adr_dic[(x,y)] = True

    house_adr_list = sorted(solution(house_adr_dic))
    print(len(house_adr_list))
    for h_set in house_adr_list: print(h_set)