[Python](BFS) 백준 2667번 : 단지번호붙이기

---

< 접근 방법 >

1. 지도 모양을 그대로 arr라는 이차원 배열에 입력한다.
2. 차례로, 방문하지 않았던 곳만을 방문하기 위해서 이차원 배열인 visited 배열도 만들어준다.
3. 각 단지의 집 개수를 모아서 저장하기 위한 size_lst를 list형태로 만들어준다.
4. 이중 for문으로 arr를 탐색하면서 방문한 적이 없으면서 집이 있는 곳(1로 표시된 곳)이 발견되면 bfs를 돌린다. (이때 새로운 단지가 발견되는 것이므로 town에 +1을 해주고, bfs의 결과값으로 집의 개수를 return해 size_lst에 추가해준다.

---

from collections import deque
def bfs(si, sj):
    q = deque()
    q.append((si, sj))
    visited[si][sj] = 1

    count = 1  # count = 집의 개수
    while q:
        ci, cj = q.popleft()
        for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)):   # 상우하좌 좌표 탐색
            ni = ci + di
            nj = cj + dj
            # 범위 내, 미방문, arr값 1의 조건을 만족한다면 count에 +1을 해주고 좌표를 q에 담기
            if 0<=ni<N and 0<=nj<N and not visited[ni][nj] and arr[ni][nj]:
                q.append((ni, nj))
                visited[ni][nj] = 1
                count += 1
    return count    # 집의 개수 return


N = int(input())
# [1] 이차원 형태의 arr 배열과 visited 배열 생성, 집의 개수를 담기위한 size_lst와 단지 수를 나타내는 town
arr = [list(map(int, input())) for _ in range(N)]
visited = [[0]*N for _ in range(N)]
size_lst = []
town = 0

# [2] 이중 for문을 돌며 1이면서 방문한 적이 없는 곳을 bfs로 돌림
for i in range(N):
    for j in range(N):
        if arr[i][j] and not visited[i][j]:
            size_lst.append(bfs(i, j))  # 집의 개수(bfs 결과값)을 size_lst에 담기
            town += 1   # 단지 수 추가

size_lst.sort() # 오름차순으로 출력하기 위해 정렬

# [3] 출력(단지수, 각 집의 개수)
print(town)
for k in size_lst:
    print(k)

 

이해가 안되는 부분이 있으면 질문 주세요. 감사합니다.