문제
접근
어제의 아기 상어와 마찬가지로 BFS와 시뮬레이션이 결합된 문제이다.
BFS 기본문제 중에 인접한 영역의 크기를 구하는 문제를 알고 있다면 생각보다 쉽게 접근할 수 있다.
문제에서 주어지는 l, r 조건에 맞는 인접 영역을 구하면 된다.
이 때 영역의 크기뿐 아니라, 영역에 속하는 좌표들도 구해와서 일괄적으로 수정해주면 된다.
프로세스는 다음과 같다.
- board 전체를 돌며 아직 방문하지 않은 곳에 대해 BFS를 수행한다.(checkVisit)
- BFS를 수행하며 방문한 좌표를 담아준다.(bfs)
- 담은 좌표들에 대해 인구수를 조정한다.(changePopulation)
- 1,2,3의 과정을 변화가 없을 때까지 반복한다.
80%에서 시간초과가 계속 떠서 어떻게 시간을 줄여야할지..
bfs 수행 후 인구수를 조정하기 전에 조정할 필요가 있는지 체크해주는 것으로 시간초과를 해결했다.
간단하게 방문한 좌표가 1개라면 수정할 필요가 없으므로 건너뛰게 해줬더니 쉽게 해결했다. 다행..
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from collections import deque
import sys
input = sys.stdin.readline
def changePopulation(board, locList, change):
isChange = False
for i, j in locList:
if board[i][j] != change:
isChange = True
board[i][j] = change
return isChange
def bfs(board, visit, n, l, r, i, j):
q = deque()
q.append((i, j))
dx = [0,0,-1,1]
dy = [1,-1,0,0]
visit[i][j] = 1
visitedArr = [(i, j)]
sumPop = board[i][j]
sumSize = 1
while q:
nowy, nowx = q.popleft()
for x, y in zip(dx, dy):
nx = nowx + x
ny = nowy + y
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if visit[ny][nx] != 0:
continue
if l <= abs(board[ny][nx] - board[nowy][nowx]) <= r:
visit[ny][nx] = 1
sumPop += board[ny][nx]
sumSize += 1
visitedArr.append((ny, nx))
q.append((ny, nx))
if sumSize == 1:
return False
changePop = sumPop // sumSize
return changePopulation(board, visitedArr, changePop)
def checkVisit(board, n, l, r):
visit = [[0]*n for _ in range(n)]
isChange = False
for i in range(n):
for j in range(n):
if visit[i][j] == 0:
if bfs(board, visit, n, l, r, i, j):
isChange = True
return isChange
def main():
n, l, r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
while True:
flag = checkVisit(board, n, l, r)
if flag:
cnt += 1
else:
break
print(cnt)
if __name__ == "__main__":
main()