Jinho Tech

기본적인 DFS & BFS 문제이다. 

DFS 풀이

def dfs(y, x, cnt):
    graph[y][x] = 0
    d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < N) and (0 <= X < N) and graph[Y][X] == 1:
            cnt = dfs(Y, X, cnt+1)
    return cnt

N = int(input())
graph = [list(map(int, list(input()))) for _ in range(N)]
res = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            res.append(dfs(i, j, 1))
res.sort()
print(len(res))
for n in res:
    print(n)

BFS 풀이

from collections import deque

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    cnt = 1
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < N) and graph[Y][X] == 1:
                queue.append((Y, X))
                graph[Y][X] = 0
                cnt += 1
    return cnt

N = int(input())
graph = [list(map(int, list(input()))) for _ in range(N)]
res = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            graph[i][j] = 0
            res.append(bfs(i, j))
res.sort()
print(len(res))
for n in res:
    print(n)