[알고리즘] 백준 2667 : 단지번호붙이기 - S1

문제링크

2023.05.03 풀이 - dfs

import sys
input=sys.stdin.readline
arr=[]
res=[]
cnt=0

n=int(input())
for _ in range(n):
    arr.append((list(map(int, input().rstrip()))))

def dfs(x,y):
    if x<0 or x>=n or y<0 or y>=n:
        return False
    if arr[x][y]==1:
        global cnt
        arr[x][y]=0
        cnt+=1
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    return False

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

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

2023.11.10 풀이 -bfs

import sys
input=sys.stdin.readline
from collections import deque

arr=[]
res=[]
dx, dy=[0,0,-1,1],[-1,1,0,0]

n=int(input())
for _ in range(n):
    arr.append(list(map(int, input().rstrip())))


def bfs(i,j):
    queue=deque()
    queue.append((i,j))
    arr[i][j]=0
    cnt=1
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<n and arr[nx][ny]==1:
                cnt+=1
                arr[nx][ny]=0
                queue.append((nx, ny))
    return cnt


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

print(len(res))
res.sort()
print(*res, sep="\n")