[백준][2667번] 단지번호붙이기 - Python3

1. 문제 설명

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

7

0110100

0110101

1110101

0000111

0100000

0111110

0111000

예제 출력 1

3

7

8

9

 

2. 접근 방법 및 풀이

- DFS 문제 유형에서 심심치 않게 볼 수 있는 유형으로 2차원 배열에서 붙어있는 1(집이 있는 곳) 들을 묶어서 단지로 정의하고 몇 개의 단지가 있는지, 단지마다 몇 개의 집이 있는지를 출력하는 문제입니다.

 

- 2차원 배열에서 1이 나오면 카운트를 증가시킨 후에 왼쪽, 오른쪽, 위쪽, 아래쪽 인덱스에 대해서 재귀적으로 DFS알고리즘을 호출하고 True를 반환한다. 그럼 카운트 갯수를 임의의 리스트에 저장하고 카운트를 초기화 해주는 방식으로 문제를 해결했습니다.

 

- 주의해야 할점은 주어진 인덱스의 범위를 벗어나는 경우에는 알고리즘을 종료하게끔 구현해주시면 됩니다!

# 2667 단지번호붙이기
 
# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
    global cnt
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x < 0 or x >= N or y < 0 or y >= N:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 1:
        # 해당 노드 방문 처리
        graph[x][y] = 0
        # 카운트 값 증가
        cnt += 1 
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False
 
    
N = int(input())
graph = []
arr = []
cnt = 0
 
for i in range(N):
    graph.append(list(map(int,input())))
    
for i in range(N):
    for j in range(N):
        if dfs(i, j) == True:   # 한 구역의 1들을 다 처리했으면 카운트 값 저장 후 초기화
            arr.append(cnt)
            cnt = 0
 
arr.sort()
print(len(arr))
 
for i in arr:
    print(i)

3. 후기

- 예전에 공부했던 내용을 토대로 DFS 알고리즘을 직접 짜보려 시도했으나, 계속되는 에러에 결국엔 기존에 정리해놓았던 알고리즘을 문제에 맞게 수정하는 형태로 해결했습니다 :(

 

- 알고리즘 강의는 유튜브 동빈나님 강의 추천드립니다!