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

0은 집이 없는 곳. 1은 집이 있는 곳.

연결된 집들끼리 이어붙인 모임을 단지라고 정의하고,

그 단지의 수와 각 단지의 집 수를 오름차순으로 출력하는 문제.

 

from collections import deque
import sys
input = sys.stdin.readline

def bfs(x, y):
    cnt = 0
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    queue = deque()
    queue.append((x, y))
	#graph[x][y] = 0 해줘야함. cnt = 1로 할 때.
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = 0
                #graph[nx][ny] = graph[x][y] + 1
                cnt += 1
    if cnt == 0:
        return cnt + 1
    else: return cnt
    

N = int(input())
graph = []
output = []
for _ in range(N):
    a = list(map(int, input().strip()))
    graph.append(a)

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            output.append(bfs(i, j))

print(len(output))
for num in sorted(output):
    print(num)

BFS를 사용해서 풀었다.

일단 for문으로 N*N 배열을 돌면서 1이 등장할 때마다 BFS함수를 호출한다.

 

BFS 함수에서는 큐에 넣어둔 좌표들을 체크할 때마다

그 좌표를 기준으로 앞뒤양옆을 갈 수 있는지 체크하고 갈 수 있으면

큐에 넣고 0으로 만든다. 그리고 집이 몇 개인지 카운팅 해준다.

이렇게하면 한 BFS 함수가 끝날 때 마다 한 단지를 전부 카운팅 했다는 뜻이다.

 

그런데 단지 안의 집이 하나일 때는 집의 갯수가 카운팅이 되지 않아서,

cnt가 0일 때는 따로 조건으로 빼줬다.

이렇게 풀어서 맞긴 맞았는데.. 별로 마음에 안 들어서 다시 봤는데,,

 

처음에 cnt를 1로 초기화 해야한다는 걸 알고는 있었는데, 그러면 정답보다 하나씩 더 큰 값들이

나오길래, 자세히 보니 시작 지점을 방문하고 0으로 바꾸지 않아서 그랬던 것이였다.