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

✔ 문제 2667 단지번호붙이기

문제 바로가기 💨 

 

⬜ 핵심 아이디어

 

arr배열을 입력받아 순회하며, 방문하지 않은 1을 만나면 bfs로 해당 점의 주변을(상하좌우) 탐색한다.

bfs에서는 q에 주변을 탐색할 점을 넣고, 상하좌우 방향을 탐색한다.

 

🖌에러해결

sys.stdin.readline이 input()과 다르게 '\n'개행문자까지 입력받는다는 사실을 놓쳐, 에러가 나서 한참 헤맸다 ㅠ

 

PYTHON

import sys

# bfs: 시작위치 받아서, 해당 위치에 연결된 1의 개수 리턴
def bfs(si, sj):
    q = []  # 큐 및 필요 변수 생성

    q.append((si, sj))  # 큐 초기 데이터 삽입
    v[si][sj] = 1  # 방문 표시
    cnt = 1  # 정답 처리 관련 작업

    while q:
        ci, cj = q.pop(0)
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ni, nj = ci + di, cj + dj
            # 4방향, 범위내, 미방문, 1이면 q 삽입
            if 0 <= ni < N and 0 <= nj < N and v[ni][nj] == 0 and arr[ni][nj]:
                q.append((ni, nj))
                v[ni][nj] = 1
                cnt += 1
    return cnt

input = sys.stdin.readline
N = int(input().strip())  # 줄 바꿈 문자 제거
arr = [list(map(int, input().strip())) for _ in range(N)]  # 줄 바꿈 문자 제거
v = [[0] * N for _ in range(N)]
ans = []

for i in range(N):
    for j in range(N):
        # 방문하지 않았던 아파트 발견시 bfs
        if arr[i][j] == 1 and v[i][j] == 0:
            ans.append(bfs(i, j))

ans.sort()
print(len(ans), *ans, sep='\n')