백준 2667 단지번호붙이기

문제 링크

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

풀이 전 계획과 생각

BFS로 상하좌우로 서로 연결되는 집을 찾아서 세어서 각 단지별 주소 수를 오름차순으로 출력하면 될 것 같다.

풀이 (코드 블록 첨부)

# 백준 2667 단지번호붙이기  
import sys
import collections
N = int(input())
#houses=[]
houses = [list(map(int,list(sys.stdin.readline().strip()))) for x in range(N)]



def bfs(loc):
    current_total=0 # 현재 단지 개수 
    visited=[[0]*(len(loc[0])) for x in range(len(loc))] #방문 여부를 기록하기 위해서 0행렬 작성 
    houses_cnts=[] #단지별로 집을 센 목록 
    houses_cnt=0 # 현재 단지의 집의 수 
    for i in range(len(loc)):
        for j in range(len(loc[0])): # 이중 반복문으로 전체 지도를 탐색 
            if loc[i][j]==0: # 0이라면 집이 없으므로 세지 않음 
                continue
            if visited[i][j]==1: # 이미 방문했으면 아까 세었으니까 세지 않음 
                continue
            #to_visit=[[i,j]]
            to_visit = collections.deque([[i,j]]) # 방문을 시작할 목록을 초기화 
            current_total+=1 # 단지 총 개수 1 증가 
            
            houses_cnt=0 # 현재 단지의 집 개수는 0으로 초기화 
            
            while to_visit: # 방문할 목록 bfs 
                
                #current_loc=to_visit.pop(0)
                current_loc=to_visit.popleft() # 목록에서 하나 popleft
                
                if visited[current_loc[0]][current_loc[1]]==0:
                    houses_cnt+=1
                    visited[current_loc[0]][current_loc[1]]=1
                    # 아직 세지 않은 주소라면 현재 단지의 집 개수 1 늘리고 방문 목록 업데이트
                    # 현재에서 상하좌우 값 정의
                to_compare = [[current_loc[0]-1,current_loc[1]],\
                              [current_loc[0]+1,current_loc[1]],\
                              [current_loc[0],current_loc[1]-1],\
                              [current_loc[0],current_loc[1]+1]]  
                # 배열의 index 범위를 벗어나면 빼고
                # 집이 있고
                # 방문하지 않았으면
                # 그렇다면 방문 목록에 추가하고 while문을 계속함 
                for element in to_compare:
                    if element[0]>=0 and element[0]<len(loc) and \
                       element[1]>=0 and element[1]<len(loc[0]) and \
                       loc[element[0]][element[1]]==1 and \
                       visited[element[0]][element[1]]==0: 
                        to_visit.append(element) 
            if houses_cnt>0: # 이번에 센 집의 개수가 0이 넘으면 단지 목록에 추가 
                houses_cnts.append(houses_cnt)
    print(current_total)
    houses_cnts.sort() # 1 이상의 집 개수가 나온 단지 오름차순 정렬 
    for element in houses_cnts:
        print(element)
bfs(houses)
    

    

풀이하면서 막혔던 점과 고민

어려운 점은 정말 많았지만 여기까지 푸는 데 너무 시간이 오래 걸려서 며칠 전에 무슨 생각을 했는지 일일이 생각이 나지 않는다 -_-;

풀이 후 알게된 개념과 소감

BFS는 언제 하는 것인지 조금 더 알게 되는 계기가 되었다.

그리고... 사실은 저게 완전히 성공한 건 아니고 백준 채점 프로그램에서는 시간초과 뜬다 ㅠㅠ

여기서 어떻게 뭘 줄이는지 현재로서는 잘 모르겠고 여기까지 하는 데도 너무 오래 걸렸기 때문에 맞았습니다!는 다음에 받아 보는 걸로... ㅠ