- 문제 : 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)'백준 > Search' 카테고리의 다른 글
| [bfs/백준] 5427번 : 불 (0) | 2023.05.22 |
|---|---|
| [bfs/백준] 2206번 : 벽 부수고 이동하기 (0) | 2023.05.20 |
| [bfs/백준] 7576번 : 토마토 (0) | 2023.05.17 |
| [bfs/백준] 6593번 : 상범 빌딩 (0) | 2023.05.16 |
| [bfs/백준] 5014번 : 스타트링크 (0) | 2023.05.16 |
