240319 [BOJ/백준] 2667. 단지번호붙이기

 

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

2667번: 단지번호붙이기

---

나의 코드

def bfs(x, y): 
    global number
    global house_num
    q.append([x, y])
    visited[x][y] = 1
    house_num = 1

    while q:
        a, b = q.pop(0)
        for k in range(4):
            ni = a + di[k]
            nj = b + dj[k]
            if 0 <= ni < N and 0 <= nj < N and arr[ni][nj] == 1 and visited[ni][nj] == 0:
                visited[ni][nj] = 1
                house_num += 1  # 방문한 집의 수 1 더함
                q.append([ni, nj])
    number += 1  # 이어진 집들 다 돌아서 단지 수 1 더함
    house_num_list.append(house_num) # 방문한 집의 수 총 합을 리스트에 저장
    return


N = int(input())
arr = [list(map(int, input())) for _ in range(N)]
visited = [[0]*N for _ in range(N)]
number = 0
house_num = 1
q = []
house_num_list = []
di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]


for i in range(N):
    for j in range(N):
        if arr[i][j] == 1 and visited[i][j] == 0:
            bfs(i, j)  # 방문하지 않은 집을 시작으로 함수 실행

print(number)
house_num_list.sort()  # 단지 내 집의 수 오름차순으로 정렬
for k in house_num_list:
    print(k)

 

결과

---

bfs의 템플릿도 어느정도 알겠고 문제에서 요구하는 바도 처음부터 잘 읽어보고 풀어봤더니 바로 성공!! 알고리즘 정체기라고 생각했는데 열심히 할 원동력이 생겼다!ㅎㅎㅎ