📌문제

📌나의 코드

• DFS 31316KB, 44ms

def dfs(x, y):
    global cnt
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False
    if map[x][y] == 1:
        map[x][y] = 0
        cnt += 1
        # 상하좌우 탐색
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        return True, cnt
    return False

n = int(input())  # 격자 크기
map = [list(map(int, input())) for _ in range(n)]

# 집의 수
homes = 0
# 단지 수
cnts = []

for i in range(n):
    for j in range(n):
        cnt = 0
        if dfs(i, j):
            homes += 1
            cnts.append(cnt)

# 단지 수 오름차순 정렬
cnts.sort()
print(homes)
for c in cnts:
    print(c)

📌다른 사람 코드

• DFS 31332KB, 44ms

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

    if map[x][y] == 1:
        cnt += 1
        map[x][y] = 0
        for i in range(4):
            nx, ny = x + dxs[i], y + dys[i]
            dfs(nx, ny)
        return True
    return False

n = int(input())
map = [list(map(int, input())) for _ in range(n)]

dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]

# 단지 수
cnt = 0
cnts = []

# 집의 수
result = 0

for i in range(n):
    for j in range(n):
        if dfs(i, j):
            cnts.append(cnt)
            result += 1
            cnt = 0

# 단지 수 오름차순 정렬
cnts.sort()

print(result)
for c in cnts:
    print(c)

• BFS 34176KB, 64ms

from collections import deque

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    map[x][y] = 0
    cnt = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dxs[i], y + dys[i]
            if nx <= -1 or nx >= n or ny <= -1 or ny >= n:
                continue
            if map[nx][ny] == 1:
                map[nx][ny] = 0
                queue.append((nx, ny))
                cnt += 1
    return cnt

n = int(input())  # 격자 크기
map = [list(map(int, input())) for _ in range(n)]

dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]

# 단지 수
cnts = []

for i in range(n):
    for j in range(n):
        if map[i][j] == 1:
            cnts.append(bfs(i, j))

cnts.sort()
print(len(cnts))
for c in cnts:
    print(c)