https://www.acmicpc.net/problem/16946
옛날에 시도 했을 때는 뭐야 쉬운 BFS네 하고 풀었지만 당연하게도 시간초과가 떴다.
그 때 어떤 방식으로 풀었는지 공부했었고 이제서야 풀게 되었다.
맵에서 인접한 0 그룹들을 방문처리하여 indexing 및 0의 개수를 저장하는 data 리스트를 만든다.
이후, 맵을 copy하여 복제 된 리스트의 값이 1인 부분마다 solve() 함수를 실행하여 인접한 0 그룹들의 개수를 더해주고 return한 값을 넣어준다.
- 여기서 copy를 안하고 answer을 수정하면 10으로 나눈 나머지가 0일 때 버그가 발생한다.
from collections import deque
from copy import deepcopy
row, col = map(int, input().split())
graph = [list(map(int, input())) for _ in range(row)]
result = deepcopy(graph)
visited = [[0 for _ in range(col)] for _ in range(row)]
cnt = 0
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
data = []
def BFS(x, y):
global cnt
cnt += 1
num_count = 1
q = deque()
q.append((x, y))
visited[x][y] = cnt
while q:
x, y = q.popleft()
for dx, dy in direction:
nx, ny = x + dx, y + dy
if nx < 0 or ny < 0 or nx >= row or ny >= col or visited[nx][ny] or graph[nx][ny]:
continue
visited[nx][ny] = cnt
q.append((nx, ny))
num_count += 1
data.append([cnt, num_count])
def solve(x, y):
temp = 0
v = []
for dx, dy in direction:
nx, ny = x + dx, y + dy
if nx < 0 or ny < 0 or nx >= row or ny >= col or graph[nx][ny]:
continue
if not visited[nx][ny] in v:
temp += data[visited[nx][ny] - 1][1]
v.append(visited[nx][ny])
return (temp + 1) % 10
for r in range(row):
for c in range(col):
if graph[r][c] == 0 and not visited[r][c]:
BFS(r, c)
for r in range(row):
for c in range(col):
if graph[r][c] == 1:
result[r][c] = solve(r, c)
for i in range(row):
print(*result[i], sep='')
