[백준] 2667번 단지번호붙이기(DFS알고리즘)(Python - 파이썬)

백준 2667번 문제입니다.  (solved.ac)기준  실버 1 문제입니다.

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

2667번: 단지번호붙이기

예제 입력 1 :

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 1 :

3
7
8
9

 

문제를 보시면 집이 있는 곳을 1, 집이 없는 곳을 0으로 나타낸다고 합니다. 집(1)이 모여있는 것을 단지라고 정의합니다.

<그림2>는 <그림1> 을 단지별로 묶어둔 그림입니다. (검은색, 붉은색, 초록색) 따라서 단지는 3개이고 각 단지별 속하는 집의 수는 

검은색은 7개 / 붉은색은 8개 / 초록색은 9개 입니다. 출력은 총 단지수와 단지별 속하는 집의 수를 오름차순으로 정렬하여 '한 줄'에 하나씩 출력하면 됩니다.

 

DFS(깊이 우선 탐색) 알고리즘을 사용하여 문제를 풀었습니다.

 

import sys
n = int(sys.stdin.readline().rstrip()) # 지도의 크기를 입력받음
graph = []
cnt = 0 # 총 단지수
global house # 전역변수로 house선언
house = 0 # 단지별 속하는 집의 수를 임시로 담을 변수
ans = [] # 리스트로 단지별 속하는 집의 수(house)를 저장

# 입력받은 좌표 및 상하좌우에 집(1)이 있는지 확인 후
# 집의 수(house), 새로운 단지 여부(True/False)를 반환
def dfs(x,y) :
    global house
    # 탐색간 그래프 범위를 넘어가면 즉시 탈출
    if x <= -1 or x >= n or y <= -1 or y >= n :
        return False

    # 탐색하는 부분이 집(1)이라면
    # 집의 수(house) 1 증가, 탐색을 했다는 의미로 1에서 0으로 값을 변경
    if graph[x][y] == 1 :
        house += 1
        graph[x][y] = 0

        # 상하좌우 반복해서 탐색
        # 상하좌우에 인접해있는 모든 집(1)에 접근하여
        # 집의 수(house) 1 증가, 탐색을 했다는 의미로 1에서 0으로 값을 변경
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        # 위의 과정을 거쳐 인접한 집(1)들의 수만큼 house의 값이 증가하고
        # 한 단지로 묶여 True로 반환
        # 예를 들어 문제와 동일하게 입력을 받았다면 (0,1)을 탐색할 때
        # 그와 인접한 곳들과 또 거기서 인접한 곳들을 모두 방문처리하여 0으로 바꿔주기 때문에
        # (0,2), (1,1), (1,2), (2,0), (2,1), (2,2)이 모두 0으로 변경되어
        # 다음 탐색부터는 False로 반환됨.
    	# 따라서 단지로 묶이고 한 번만 True값으로 반환이 된다.
        return True

    return False




for _ in range(n) : # 지도의 크기(n) 만큼 그래프에 지도 정보를 입력받음
    graph.append(list(map(int,sys.stdin.readline().rstrip())))

for i in range(n) : # 지도의 크기만큼 탐색을 실시
    for j in range(n):
        if dfs(i,j) == True : # 단지별로 묶여서 True로 반환됨.
            cnt += 1 # dfs가 True라면 단지가 생성된 것이므로 단지 수(cnt) 1 증가
            ans.append(house) # 리스트에 집의 수(house)를 넣어줌.
            house = 0 # 다음 단지에서는 집의 수를 별도로 세야하기 때문에 집의 수를 0으로 초기화

ans.sort() # 문제에서 집의 수를 오름차순으로 출력하라했으니 sort()함수를 사용하여 정렬
print(cnt) # 단지수 출력
for i in ans :
    print(int(i)) # 오름차순으로 정렬된 ans리스트를 한 줄에 하나씩 출력