BOJ 2667 단지번호붙이기

https://www.acmicpc.net/problem/2667
시간 1초, 메모리 128MB
input :

• N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)
• N개의 자료(0(집 X)혹은 1(집))

output :

• 총 단지수를 출력
• 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력

조건 :

• 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 상, 하, 좌, 우로 다른 집이 있는 경우를 말한다.
  

---

상, 하, 좌, 우 움직이는 건.

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

    while q:
        now_x, now_y = q.popleft()

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

리스트에 챙겨넣은 다음에 반복문 돌려서 모든 경우를 확인.

visit 리스트의 경우에 집이 있는것은 1이고 없으면 0이니까 체크를 하면서 0으로 업데이트를 하자.

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

BFS 내부에 현재 단지내의 집의 수를 세아리는 cnt 변수를 넣어서 마지막에 리턴 시키자. 이를 통해 단지 내 집의 수를 정렬 해서 출력해 줄 수 있다.

정답 코드 :

import sys
from _collections import deque

n = int(sys.stdin.readline())
graph = []
for i in range(n):
    graph.append(list(sys.stdin.readline().strip()))
group = []

def BFS(x, y):
    q = deque([(x, y)])
    graph[x][y] = '0'
    cnt = 1
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    while q:
        now_x, now_y = q.popleft()

        for i in range(4):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if nx < 0 or nx >= n or ny >= n or ny < 0:
                continue
            if graph[nx][ny] == '1':
                graph[nx][ny] = '0'
                cnt += 1
                q.append((nx, ny))
    return cnt

for i in range(n):
    for j in range(n):
        if graph[i][j] == '1':
            group.append(BFS(i, j))
print(len(group))
group.sort()
for item in group:
    print(item)