[백준]2667 단지번호붙이기 Python

[백준]2667 단지번호붙이기 Python

이 문제는 for문을 돌아가면서 BFS 또는 DFS 구현 시 return 값을 list에 저장 후 오름차순으로 정렬하여 프린트 하면 된다.
graph 값을 바꿔가면서 수를 셀까 고민했는데 그냥 cnt를 선언하여 count하고, 지나간 값을 0으로 바꾸는 방식으로 구현했다.

from collections import deque
import sys
sys.stdin=open("input.txt")

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

#북동남서
dx=[-1,0,1,0]
dy=[0,1,0,-1]


def dfs(graph,si,sj):
    global cnt
    graph[si][sj]=0

    for i in range(4):
        nx=si+dx[i]
        ny=sj+dy[i]

        if 0<=nx<n and 0<=ny<n and graph[nx][ny]==1:
            graph[nx][ny]=0
            cnt+=1
            dfs(graph,nx,ny)

    return cnt

def bfs(graph,si,sj):
    q=deque()
    q.append((si,sj))
    cnt=1
    graph[si][sj]=0

    while q:
        x,y=q.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]

            if 0<=nx<n and 0<=ny<n and graph[nx][ny]==1:
                graph[nx][ny]=0
                cnt+=1
                q.append((nx,ny))


    return cnt




result=[]
for i in range(n):
    for j in range(n):
        if graph[i][j]==1: #DFS 혹은 BFS 수행
            #result.append(bfs(graph,i,j))
            cnt=1
            result.append(dfs(graph,i,j))

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