백준 [2667] 단지번호붙이기 (파이썬 풀이)

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

2667번: 단지번호붙이기

 

나의 풀이

import sys
import collections
n = int(sys.stdin.readline().strip())
matrix=[[int(x)for x in sys.stdin.readline().strip()]for _ in range(n)]
#행렬 조회
def dfs(x,y,visited,matrix):
        visited[x][y]=1
        global nums
        if matrix[x][y]==1:
            nums+=1    
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<len(matrix) and 0<=ny<len(matrix[0]):
                if visited[nx][ny]==0 and matrix[nx][ny]==1:
                    dfs(nx,ny,visited,matrix)
                    
def solution(matrix,n):
    visited=[[0]*n for _ in range(n)]
    global nums
    numlist=[]
    nums=0  
    for a in range(n):
        for b in range(n):
            if matrix[a][b]==1 and visited[a][b]==0:
                dfs(a,b,visited,matrix)
                numlist.append(nums)    
                nums=0 # 새로운 단지의 집 개수 조회를 위해 초기화
              
    print(len(numlist))
    for n in sorted(numlist):
        print (n)
        
dx=[-1,1,0,0] #좌우 조회
dy=[0,0,1,-1] #상하 조회
nums=0
solution(matrix,n)

행렬에서 요소 하나를 탐색할때 요소 상하좌우도 함께 탐색을 해야하기 때문에 dfs 탐색을 이용했다.

구열 별로 nums를 구한뒤 numlist에 넣어준다.

마지막으로 numlist의 길이를 프린트해 단지의 개수를 구하고

for문을 돌려 numlist의 요소를 하나씩 프린트해 단지 별 집의 개수를 구해준다.