[bfs/백준] 16234번 : 인구 이동

- 문제 : https://www.acmicpc.net/problem/16234

 

문제 이해 

- 특정 지점을 중심으로 bfs 탐색을 하면서 조건에 만족하는 노드를 모은 다음 전체의 평균으로 값을 업데이트하는 문제다.

- bfs 로직은 그렇게 어렵지 않았는데, 헷갈렸던 부분이 어떤 부분으로 bfs를 시작할지였다. while문에 이중 for문을 사용해야할 것 같은데 문제보니까 같은 지점도 중복으로 인구이동을 하는 것 같은데 이거를 어떻게 해야할지 몰랐다.

- 그래서 풀이를 보니까 while문을 시작할 때 visit를 초기화해서 방문하지 않은 지점을 중심으로 bfs를 하고, bfs 하면서 조건을 만족했던 지점들을 배열로 문제를 해결했다. 

- 반환한 배열(result)을 조건에 따라 인구이동을 하면 된다.

 

풀이 로직 

- n, l, r 과 matrix를 입력값으로 받는다. 

- while문을 돌면서 visit를 새로 설정하고 이중 for문을 돌면서 방문하지 않은 지점들을 중심으로 bfs를 진행한다. bfs를 통해 인구이동을 할 수 있는 노드들의 위치를 result로 가져온다. 이때 인구이동을 하므로 flag = True로 설정한다.

- result의 원소 개수가 2개 이상이라면 인구 이동을 할 수 있으므로 인구이동을 한다. 

인구 이동 로직은 다음과 같다. 각 지점의 matrix 값을 모두 더한 다음에 전체 개수를 나눠서 각 result 지점에 덮어씌워주면 된다. 

# 인구 이동을 할 수 있을 때
if len(result) >= 2:
	flag = True
	total = 0
	for i, j in result:
		total += matrix[i][j]
		temp = total // len(result)
	for i, j in result:
		matrix[i][j] = temp

- 더이상 인구 이동을 하지 않으면 이중 for문을 나왔을 때 flag == False 이므로 그때 while문을 나와주고, 아니라면 다시 처음부터 시작한다.

 

정답 풀이 

- bfs

def bfs(x, y, matrix, visit):
    visit[x][y] = 1
    result = [[x, y]]
    queue = [[x, y]]
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if not visit[nx][ny] and l <= abs(matrix[nx][ny] - matrix[x][y]) <= r:
                    visit[nx][ny] = 1
                    queue.append([nx, ny])
                    result.append([nx, ny]) 
    return result

 

- 인구 이동

# 인구 이동을 할 수 있을 때
if len(result) >= 2:
	flag = True
	total = 0
	for i, j in result:
		total += matrix[i][j]
		temp = total // len(result)
	for i, j in result:
		matrix[i][j] = temp

 

- 전체 코드

def bfs(x, y, matrix, visit):
    visit[x][y] = 1
    result = [[x, y]]
    queue = [[x, y]]
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if not visit[nx][ny] and l <= abs(matrix[nx][ny] - matrix[x][y]) <= r:
                    visit[nx][ny] = 1
                    queue.append([nx, ny])
                    result.append([nx, ny]) 
    return result
    
n, l, r = map(int, input().split())
matrix = []
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
for _ in range(n):
    matrix.append(list(map(int, input().split())))
    
answer = 0
while True:
    flag = False
    visit = [[0] * n for _ in range(n)]
    for x in range(n):
        for y in range(n):
            if not visit[x][y]:
                result = bfs(x, y, matrix, visit)
                # 인구 이동을 할 수 있을 때
                if len(result) >= 2:
                    flag = True
                    total = 0
                    for i, j in result:
                        total += matrix[i][j]
                    temp = total // len(result)
                    for i, j in result:
                        matrix[i][j] = temp
                                       
    if flag == False:
        break
        
    answer += 1
        
print(answer)