[dfs/백준] 2667번: 단지번호 붙이기

-문제 : https://www.acmicpc.net/problem/2667

 

스스로 푼 문제다! 전에 풀었을 때는 아쉽게 답지를 봤던 것 같은데, 이번에는 5트만에 정답이었다

dfs문제이고, gloabl count로 각 단지의 수를 구하는 것이 요점인 것 같다. 

그리고 탐색 시작하는 지점 방문처리하고 시작하는 것도!

 

-정답 풀이 :

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input())))
dx=[-1,1,0,0]
dy=[0,0,-1,1]
result=[]

def dfs(x,y):
    global count
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0<= ny < n :
            if data[nx][ny] and not visit[nx][ny]:
                visit[nx][ny]=1
                count+=1
                dfs(nx,ny)  
    
visit=[[0]*n for _ in range(n)]                
for i in range(n):
    for j in range(n):
        if not visit[i][j] and data[i][j]==1:  
            visit[i][j]=1
            count=1
            dfs(i,j)
            result.append(count)

            
print(len(result))            
result.sort()
for i in range(len(result)):
    print(result[i])