백준_2667_단지번호붙이기

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

2667번: 단지번호붙이기

 

문제요약)

<그림 1>과 같이 정사각형의 모양의 지도에서 1은 집이 있는 곳, 0은 집이 없는 곳이다.

대각선을 제외하고 좌우, 위아래로 연결된 집의 모임을 단지라고 정의한다.

<그림 2>는 <그림 1>을 단지별로 번호를 붙인것이다.

단지수와 각 단지에 속하는 집의 수를 오름차순으로 정렬하라.

 

 

입력)

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

 

출력)

 

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

 

풀이포인트)

지도 전체를 돌면서 탐색하고 탐색 중 1인 부분은 다시 방문하지 않기 위해 0으로 바꿔 방문처리를 한다.

위아래, 좌우의 1을 탐색해 0으로 바꾸면 단지 하나를 완성한다.

모든 정점을 방문하고 가까운 1을 탐색해 단지를 완성하는 것이기 때문에 가까운 곳부터 방문하는 BFS를 수행한다.

 

풀이)

from collections import deque #collections에서 deque를 불러온다.

#각 집으로 이동할 좌표 -> 상하좌우
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

#입력받을값
n = int(input()) #테스트 케이스 개수 입력받기
graph = [] #이동횟수를 기록 할 그래프
for i in range(n): #테스트 개수만큼 반복한다.
	graph.append(list(map(int, input()))) #위치를 입력받고 그래프에 추가

#bfs
def bfs(graph, a, b): #매개변수 graph, a, b를 가지는 bfs 함수
	n = len(graph) #지도의 크기 -> len -> 공백 포함 한 그래프로 변환
    queue = deque() #queue를 deque로
    queue.append((a, b)) #queue 맨 끝에 새로운 요소 a, b 추가
    graph[a][b] = 0 #좌표 a, b를 가지는 2차원 배열의 그래프
    count = 1 #단지 수 초기화
    
    while queue: #queue내에 아무것도 안남을 때 까지 반복한다.
    x, y = queue.popleft() #queeue에서 popleft한 x, y
    for i in range(4): #현재 위치를 기준으로 4방향을 모두 구한다.
    	
        #현재 값 + 이동위치 = 신규위치
    	nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or nx >=n or ny < 0 or ny >= n: #범위 안에 위치 하지 않으면
        	continue #되돌아가기
        if graph[nx][ny] == 1: #1에 방문했으면
        	graph[nx][ny] = 0 #재방문 방지를 위해 0으로 바꾼다
            queue.append((nx, ny)) #현재 위치를 queue에 추가하고
            count+= 1 #단지수 추가하기
    return count #총 단지수 반환
    
count = [] #단지
for i in range(n): #테스트 케이스 개수만큼 반복한다
	for j in range(n):
    	if graph[i][j] == 1: #graph가 1이면
        	count.append(bfs(graph, i, j)) #bfs함수 실행한 횟수 추가
            
count.sort() #단지내 집의 수 오름차순으로 정렬
print(len(count)) #단지 수 출력
for i range(len(count()): #단지 수 만큼
	print(count[i]) #단지내 집의 수 출력