https://www.acmicp.net/problem/16946
from collections import deque
n, m = map(int, input().split())
check = [[False] * m for _ in range(n)]
a = [list(map(int, list(input()))) for _ in range(n)]
group = [[0] * m for _ in range(n)]
group_size = []
group_number = 1
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(n1, n2):
queue = deque()
queue.append((n1, n2))
check[n1][n2] = True
group[n1][n2] = group_number
count = 1
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if a[nx][ny] == 0 and not check[nx][ny]:
check[nx][ny] = True
queue.append((nx, ny))
group[nx][ny] = group_number
count += 1
group_size.append(count)
for i in range(n):
for j in range(m):
if not check[i][j] and a[i][j] == 0:
bfs(i, j)
group_number += 1
for i in range(n):
for j in range(m):
if a[i][j] == 0:
print(0, end='')
else:
near = set()
for k in range(4):
nx, ny = i + dx[k], j + dy[k]
if 0 <= nx < n and 0 <= ny < m:
if a[nx][ny] == 0:
near.add(group[nx][ny])
ans = 1
for g in near:
ans += group_size[g - 1]
print(ans % 10, end='')
print()
일단 맨 처음 빈 칸을 모두 그룹지어 그 개수를 구해줌.
벽을 비웠을 때 인접한 칸이 미리 만들어 둔 빈 칸 그룹에 포함된다면
그 그룹의 수 + 자기 자신을 더해주면 되는데
bfs는 한번만 돌려주면 됨(처음 빈칸을 그룹 지을때)
그 뒤 matrix에서 벽인 부분만을 찾아 인접 4칸을 순회하며
첫 bfs에서 지정해 둔 그룹인지만 파악해주고
그룹이라면 그 그룹의 수를 더해줌.
'백준 알고리즘 (Baekjoon Algorithm)' 카테고리의 다른 글
[파이썬] 백준 알고리즘 No.10815 숫자 카드 (0) | 2022.02.11 |
---|---|
[파이썬] 백준 알고리즘 No.11286 절댓값 힙 (0) | 2022.02.04 |
[파이썬] 백준 알고리즘 No.14502 연구소 (0) | 2022.01.26 |
[파이썬] 백준 알고리즘 No.16948 데스 나이트 (0) | 2022.01.26 |
[파이썬] 백준 알고리즘 No.16928 뱀과 사다리 게임 (0) | 2022.01.26 |