백준 2667 단지번호붙이기 파이썬

백준 2667 단지번호붙이기 풀이

접근방식

1. BFS 알고리즘을 활용하여 해결합니다.
2. 우선 단지의 수를 저장할 변수, 각각의 단지에 속하는 집의 갯수를
   저장하는 변수, 이를 저장할 리스트를 생성합니다.
3. 상하좌우 탐색을 위해 dr, dc 리스트를 활용합니다.
4. 우선 q를 덱으로 지정해주고, 첫 좌표를 append시켜줍니다.
5. 이때, 첫 좌표를 for문을 통해서 처음 발견하는 1의 위치를 넣어주게 되므로
6. append 시킨 이후 해당 위치를 0으로 바꿔줍니다.
7. 또한 즉시 집의 수를 1로 지정해줌으로써 이후 집이 늘어날 때마다 더해줍니다.
8. 이후에는 다른 BFS 문제나 좌표 이동 문제처럼 탐색 후 1인 위치를 덱에 넣어줍니다.
9. bfs함수를 2중 for문을 통해 1인 위치를 찾아주고 그 위치를 bfs 인자로 넣어줍니다.
10. 단지의 수는 각각의 단지를 저장한 리스트의 길이라는 것을 알 수 있습니다.

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

arr = []

for _ in range(n):
    arr.append(list(map(int, input())))

# 각각 단지
house_list = []
each_house = 0

# 상우하좌
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def bfs(arr, a, b):
    n = len(arr)
    q = deque()
    q.append((a, b))
    arr[a][b] = 0
    each_house = 1

    while q:
        x, y = q.popleft()
        for i in range(4):
            nr = x + dr[i]
            nc = y + dc[i]
            if nr < 0 or nr >= n or nc < 0 or nc >=n:
                continue
            if arr[nr][nc] == 1:
                arr[nr][nc] = 0
                q.append((nr, nc))
                each_house += 1
    return each_house
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            house_list.append(bfs(arr, i, j))

house_list.sort()
print(len(house_list))

for i in range(len(house_list)):
    print(house_list[i])

해당 문제는 실버1레벨의 DFS, BFS 문제였습니다.

dr, dc 리스트를 활용하거나 deque 자료구조를 활용하여 탐색을 하는 것은

다른 문제들과 동일했고, 이 문제에서의 차이점은 각각의 단지에 해당하는

집의 수를 어떻게 더해줄 것인지, 그리고 시작 위치를 어떻게 지정해줄 것인지라고 생각합니다.

해당 요인들을 잘 고려하여 푸는 것이 중요합니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady