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

문제

나의 답안

n=int(input())
g=[]
for i in range(n):
    g.append(list(map(int,input()))) #입력받은 값 저장

cnt=0

#상하좌우 탐색
dx=[1,-1,0,0]
dy=[0,0,-1,1]

def dfs(x,y):
    global cnt
    
    if x<0 or x>=n or y<0 or y>=n:#범위를 넘어선다면
        return False#반환

    if g[x][y]==1:#단지수 증가
        cnt+=1
        g[x][y]=0#방문한 지점을 0으로 바꿔 다시 방문하지 않도록 한다.
        for i in range(4):#상하좌우 이동
            nx=x+dx[i]
            ny=y+dy[i]
            dfs(nx,ny)#다시 탐색
        return True #탐색 종료
    
count=[]#단지 저장

for i in range(n): 
    for j in range(n):
        if dfs(i,j)==True:#탐색
            count.append(cnt)#cnt값 추가
            cnt=0 #초기화
            
count.sort()#오름차순 정렬
print(len(count))#개수 출력
for i in count:#단지 접근
    print(i)

접근 방법

• dfs 문제이므로 재귀로 풀어주었다.
• dfs함수를 정의해 방문한 지점은 0으로 바꿔 다시 방문하지 않도록 해 단지 별 가구의 수를 세어준다.
  방문했던 곳을 기준으로 상하좌우 탐색을 반복하고, 만약 집이 있다면 탐색을 지속하고 True를 반환한다.
• count 배열에는 단지를 저장하고, n*n에 대해 반복문으로 접근해주어 true값이면 count 배열에 가구의 수(cnt)를 저장하고 초기화해준다.
• 이후 오름차순으로 정렬하고, 문제의 요구사항을 출력해준다.