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

<문제>

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

<풀이>-BFS알고리즘사용!!

1. 그래프에서 집이 있는곳의 방문여부를 저장할 visited 배열을 선언한다.(초기값은 전부 미방문,즉 False로 선언)
2. 집이 있는곳에서 출발해 인접한 네 방향의 위치를 확인한다. 이때 그래프의 값이 1인곳이면서(즉 집이 있는곳)동시에 아직 방문하지 않은경우 해당위치를 queue에 삽입한다. 그리고 단지의 크기를 저장할 total(초기값=1)변수에 1을 더해준다. (※ 해당위치의 값이 1이여도 이미 방문한경우 queue에 삽입해서는 안된다. queue에 삽입한다는것 자체가 방문을 의미)
3. 큐에 가장먼저 들어온 곳의 위치를 추출한후 다시 인접한 곳의 위치를 확인한다.
4. 위 2,3번과정을 queue가 빌때까지 반복한다.
5. queue가 비었을 경우 total 값을 1로 다시 초기화한다.
6. graph를 이중반복문을 통해 돌면서 값이 1이고 아직 미방문한 위치에서 위의 2~5번과정을 반복한다.

<코드>-파이썬

import sys
from collections import deque
n = int(sys.stdin.readline())
graph = []
result = []
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().rstrip())))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visited = [[False]*n for _ in range(n)]
def bfs(x,y):
    total = 1
    queue = deque()
    queue.append((x,y))
    while queue:
        x,y = queue.popleft()
        visited[x][y] = True
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=n:
                continue
            if graph[nx][ny] == 0:
                continue
            if ((graph[nx][ny] == 1) and (not visited[nx][ny])):
                queue.append((nx,ny))
                total+=1
                visited[nx][ny] = True
    result.append(total)
    total = 1

for i in range(n):
    for j in range(n):
        if ((not visited[i][j]) and (graph[i][j] == 1)):
            bfs(i,j)
print(len(result))
result.sort()
for i in result:
    print(i)