백준 2667번 Python / DFS

깊이 우선 탐색(DFS)이란?

https://seokii.tistory.com/30

[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)이란?

깊이 우선 탐색 알고리즘 개념에 대한 내용입니다.

 

문제 링크

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

2667번: 단지번호붙이기

 

풀이

n = int(input())
graph = []
num = []
for _ in range(n):
    graph.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 0

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1:
        global cnt
        cnt += 1
        graph[x][y] = 0
        for i in range(4):
            nx = dfs(x+dx[i], y+dy[i])
        return True

for i in range(n):
    for j in range(n):
        if dfs(i, j) == True:
            num.append(cnt)
            cnt = 0

print(len(num))
num.sort()
for i in num:
    print(i)