[백준/BOJ] 2667번 : 단지번호붙이기 _Python

2667번: 단지번호붙이기

 

>문제

>접근방법

   그래프 전체를 탐색하면서 1인 부분은 재귀적 깊이우선탐색을 수행한다. 한 단지를 다 탐색하면 집의 수를 리스트에 추가하고 sort로 오름차순으로 정렬해준다. 여기서 리스트의 길이가 곧 단지의 수가 된다.

 

 

>풀이법

   주석으로 대체

 

 

>코드

import sys
# 런타임 에러(재귀 에러) 예방을 위해 재귀에 제한을 줌
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 상하좌우 탐색용 인덱스 변수
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

# 지도의 크기 입력받음
N = int(input())

# 단지의 정보를 지도의 크기만큼 입력받음
graph = [list(map(int, input().rstrip())) for _ in range(N)]

num = [] # 집의 개수를 담을 리스트
cnt = 0 # 집의 개수를 세기 위한 변수

# 깊이우선탐색(재귀)
def dfs_rec(x, y):
    global cnt
    cnt += 1
    
    graph[x][y] = 0 # 방문 확인을 위해 값을 1에서 0으로 변경
    
    # 상하좌우 탐색을 위해 4번 반복
    for i in range(4):
        a, b = dx[i]+x, dy[i]+y # 해당 위치를 기준으로 상, 하, 좌, 우의 인덱스를 a, b에 대입
        
        # 지도의 범위를 넘어가지 않으면서 집이 있는(1) 경우라면
        if 0 <= a < N and 0 <= b < N and graph[a][b] == 1: 
			# 재귀적으로 함수 호출(위 과정 반복)
			dfs_rec(a, b)

# 지도 전체를 탐색 (지도는 N*N 정사각형 모양임)
for j in range(N):
    for k in range(N):
    	# 집이 있다면(1)
        if graph[j][k] == 1:
            cnt = 0 # 집의 개수를 세기 위한 변수 리셋
            dfs_rec(j, k) # 집의 개수 세기
            num.append(cnt) # 집의 개수를 num 리스트에 삽입

# 리스트를 오름차순으로 정렬 
num.sort() 

# 리스트의 길이가 곧 단지의 개수이기 때문에 길이 출력
print(len(num))
# 정렬된 집의 개수 순서대로 출력
for i in num:
    print(i)

 

 

>결과

 

 

>결론 

오랜만에 푸니까 재밌다. 약 보름 만이네