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으로 바꾸지 않아서 그랬던 것이였다.