[BAEKJOON] No.2667 Python

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

2667번: 단지번호붙이기

 

 

DFS방식으로 해결

n = int(input())
graph = []
num = []

for i in range(n):
    graph.append(list(map(int, input()))) #단지 2차원 배열

dx = [0, 0, 1, -1] #상하좌우 이동탐색할 배열
dy = [1, -1, 0, 0]


def DFS(x, y):
    if x < 0 or x >= n or y < 0 or y >= n: #탐색의 끝일때 return
        return False

    if graph[x][y] == 1: 
        global count
        count += 1
        graph[x][y] = 0 #탐색 완료된 곳은 0으로 바꿈
        for i in range(4): #재귀문을 이용하여 단지의 끝까지 탐색
            nx = x + dx[i]
            ny = y + dy[i]
            DFS(nx, ny)
        return True
    return False


count = 0
result = 0

for i in range(n):
    for j in range(n): 
        if DFS(i, j) == True: #1인곳을 찾기만 하면 끝까지 탐색 후 true
            num.append(count) #단지 내 집 개수
            result += 1 #단지 개수
            count = 0 #다음 단지를 위해 초기화

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