백준 / DFS / 2667 : 단지번호 붙이기 / 파이썬

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다.

1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.

철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.

여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.

대각선상에 집이 있는 경우는 연결된 것이 아니다.

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

지도를 입력하여 단지수를 출력하고,

각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고,

그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

 

출력

첫 번째 줄에는 총 단지수를 출력하시오.

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

 

예시

 

나의 풀이 과정

1. 우선 각 input 줄들을 받아 2차원 리스트를 만들어 줍니다.

2. 2중 for문을 사용하여 해당 2차원 리스트를 돌며 값이 1인 element를 찾습니다.

3. 1을 찾았다면 해당 element의 동서남북 방향으로 1을 찾는 함수를 실행합니다. (재귀)

4. 1을 찾을때마다 단지내 집의 수에 1을 더해줍니다.

5. 더이상 인접한 1이 없으면 재귀를 종료합니다. 이때 총 단지수에 1을 더해줍니다.

6. 모든 과정이 끝나고 각 단지의 집의 수를 오름차순 정렬하여 출력합니다.

 

나의 코드

matrix = [] #2차원 리스트가 될 변수
n = int(input()) #2차원 리스트의 가로세로 길이

#각 줄의 숫자를 하나씩 떼어 list화시킨다.
#ex: 01011 -> [0,1,0,1,1]
for _ in range(n):
    matrix.append(list(map(int, input())))

#answer의 0번 index는 총 단지수를 나타낼 용도 (초기값 0)
#cnt는 집의 수를 체크할 용도
answer, cnt = [0], 0

def dfs(i, j):
    global cnt #재귀를 쓸 것이기 때문에 global cnt를 받아와야 함
    
    #i와 j의 값이 리스트 인덱스를 벗어나면 종료
    if i >= n or i < 0 or j >= n or j < 0:
        return False
    
    #element가 0이면 종료
    if matrix[i][j] == 0:
        return False

    #1이면 0으로 바꾸고 cnt + 1
    matrix[i][j] = 0
    cnt += 1

    #4방향 dfs 재귀호출
    dfs(i+1,j)
    dfs(i,j+1)
    dfs(i-1,j)
    dfs(i,j-1)

    #단지가 있음을 알리는 True를 return
    return True

#2차원 리스트 돌기
for i in range(n):
    for j in range(n):
        # 단지가 있다면 search는 True
        search = dfs(i,j)
        if search:
            answer[0] += 1
            answer.append(cnt) #해당 단지의 집 수 저장
            cnt = 0 #cnt값 초기화

#0번 인덱스는 단지수니까 제외하고 나머지만 오름차순 정렬
answer = answer[:1] + sorted(answer[1:])

print(*answer, sep='\n')

 

결과