[Algorithm🧬] 백준 2667 : 단지번호붙이기

문제

DFS

import sys

# 원래 생각했떤 것.... 상하좌우 다 확인해서 갈 수 있으면 윗쪽으로 계속 뻗어나가고 안되면 하 안되면 좌 안되면 우 ...
# 근데 뭔가 BFS 식의 코드랑 섞어서 짠듯... 
# def DFS(i, j):
#     global cnt
#
#         for x, y in adj:
#             if not 0 <= i < n:
#                 return
#
#             if not 0 <= j < n:
#                 return
#
#             if apartment[i][j] == 1 and ch[i][j] == 0:
#                 ch[i][j] = 1
#                 cnt += 1
#                 DFS(i + x, j + y)


# 그래프가 아니면 False
# 그래프가 있다면 해당 연결성분을 다 돌고 나와야 True
def DFS(i, j):
    if not 0 <= i < n:
        return False

    if not 0 <= j < n:
        return False


    if apartment[i][j] == 1 and ch[i][j] == 0:
        global cnt
        cnt += 1
        ch[i][j] = 1 # apartment[i][j] = 0 으로 막아서 해당 부분으로 다시 못가게 막아도 되더라..
        for x, y in adj:
            DFS(i + x, j + y)
        return True
    return False




n = int(sys.stdin.readline())
apartment = [[int(c) for c in sys.stdin.readline().strip()] for _ in range(n)]
ch = [[1 if apartment[i][j] == 0 else 0 for j in range(n)] for i in range(n)]


adj = [(-1, 0), (1, 0), (0, -1), (0, 1)]

apart = []
cnt = 0

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


apart.sort()
print(len(apart))
for cnt in apart:
    print(cnt)

BFS

import sys
from collections import deque

def BFS(i, j):
    q = deque()

    ch[i][j] = 1
    q.append((i, j))
    cnt = 1


    while q:
        i, j = q.popleft()

        for x, y in adj:
            if not 0 <= i + x < n:
                continue
            if not 0 <= j + y < n:
                continue

            if apartment[i + x][j + y] == 1 and ch[i + x][j + y] == 0:
                ch[i + x][j + y] = 1
                cnt += 1
                q.append((i + x, j + y))

    return cnt





n = int(sys.stdin.readline())
apartment = [[int(c) for c in sys.stdin.readline().strip()] for _ in range(n)]
ch = [[1 if apartment[i][j] == 0 else 0 for j in range(n)] for i in range(n)]

adj = [(-1, 0), (1, 0), (0, -1), (0, 1)]
sol = []

cnt = 0
q = deque()

for i in range(n):
    for j in range(n):
        if apartment[i][j] == 1 and ch[i][j] == 0:
            sol.append(BFS(i, j))


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