[백준 2667] 단지번호붙이기 (python)

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

2667번: 단지번호붙이기

단지번호 붙이기 문제

N * N 크기의 정사각형의 칸에 이어진 숫자 단지들의 총 개수와 각 단지의 크기를 구하는 문제

BFS개념을 활용하여 해결할 수 있었다.

📌 문제 접근 포인트

1. 마을의 수를 탐색하고, 이어진 칸을 확인하는 것이므로 너비 탐색(BFS)을 이용하여 탐색을 진행해 주자.
2. 방문처리와 탐색을 동시에 진행하고, 리스트를 하나 만들어줘서 탐색하면서 세어준 개수를 넣어주자. 또 진행하는 과정에서 모든 칸을 탐색하는데 기존 칸이 남아있으면 중복해서 세어버리는 상황이 나타날 수 있으니 기존 탐색한 칸은 0으로 초기화하자.
3. 만든 리스트를 오름차순으로 정렬하고, 리스트 내용물을 출력하면 완성

⚙ 내가 푼 정답코드

def complexs(a,b):
    visited = [[0]*N for _ in range(N)] # 방문 처리
    queue = [[a,b]]
    visited[a][b] = 1
    cnt = 0 # 횟수를 세어보자
    while queue:
        cnt += 1 # 갈수 있는 단지들을 세보자
        y, x = queue.pop(0)
        for dy, dx in move:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < N and visited[ny][nx] == 0 and town[ny][nx] != 0:
                visited[ny][nx] = 1 # 지나옴 체크
                town[ny][nx] = 0 # 마을 수 셋으니 이후에 안세게 건물 부숴버림
                queue.append([ny,nx])
    return cnt
        
import sys
N = int(sys.stdin.readline())
town = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
move = [[1,0],[-1,0],[0,1],[0,-1]]
result = []
for i in range(N):
    for j in range(N):
        if town[i][j] == 1: # 1로 시작하면 단지이므로
            result.append(complexs(i,j)) # 돌려서 결과에 삽입
result.sort() # 오름차순 정렬
print(len(result))
for k in range(len(result)):
    print(result[k])