코테 백준 2667 실버1

백준 2667

정말 bfs 기초문제인것 같았다. 아직 실버단계라서 그런지 문제 풀이 패턴이 이전의 풀었던 풀이법과 거의 같다고 할 수있다. 복습용으로 문제를 풀어보았고 bfs는 골드부터 블로그를 작성해야겠다.

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

n=int(input())

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

total=[]

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

def bfs(graph,i,j):
    que=deque()
    que.append((i,j))
    cnt=1
    graph[i][j]=0

    while que:
        y,x=que.popleft()
        for i in range(4):
            new_y=y+dy[i]
            new_x=x+dx[i]
            if (0<=new_x<n) and (0<=new_y<n) and graph[new_y][new_x]==1:
                cnt+=1
                que.append((new_y,new_x))
                graph[new_y][new_x]=0
    return cnt

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

print(len(total))
for i in sorted(total):
    print(i)