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

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

2667번: 단지번호붙이기

 

 

# 조건

• 정사각형 모양의 지도가 있다.
• 1은 집이 있는 곳, 0은 집이 없는 곳
• 연결된 집의 모임의 단지를 정의하는데, 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다
• 총 단지수를 출력하고 각 단지에 속하는 집의 수를 오름차순으로 출력하라.

 

# 접근 방법 및 solution

• 델타 함수를 이용한 dfs를 이용하여 연결된 단지를 체크해준다.
• 방문한 집들의 값을 0으로 변경해주고, 반복문을 돌리며 새로운 단지를 계속 찾아 다닌다.
• 원본 리스트를 건드리므로 따로 방문 리스트를 만들어주지 않아도 된다.
• 또한 각 단지마다 카운트를 해주며 결과를 저장해준다.
• dfs를 돌며 중요한 점은 단지는 이어져있지 않기 때문에, 전체를 순회하는 반복문 내에서 dfs함수로 들어가주어야 한다.

 

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
di, dj = [-1,1,0,0], [0,0,-1,1]  
# 시작위치 받아주기  
def dfs(x,y):  
    global cnt, result  
    stack = []  
    stack.append((x,y))  
    apart[x][y] = '0'  
  
    while stack:  
        sti, stj = stack.pop()  
        for k in range(4):  
            ni, nj = di[k] + sti, dj[k] + stj  
            if 0<=ni<N and 0<=nj<N and apart[ni][nj] == '1':  
                stack.append((ni,nj))  
                apart[ni][nj] = '0'  
                cnt +=1  
    result.append(cnt)  
  
  
N = int(input())  
apart = [list(input().rstrip()) for _ in range(N)]  
  
# 가구 수 저장  
result = []  
  
# 반복문 돌리면서 찾아주기  
# 이 때, apart 리스트를 그대로 써주면 안된다.  
# dfs를 돌리며 apart 리스트의 값을 바꿔줄 것이기 때문.  
for i in range(N):  
    for j in range(N):  
        if apart[i][j] == '1':  
            cnt = 1  
            dfs(i,j)  
  
print(len(result))  
result.sort()  
for l in result:  
    print(l)