Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 백준 15685
- 백준 16719
- sql 기술면접
- Spring
- 백준 17779
- 프로래머스
- 백준
- 백준 17626
- 백준 16235
- with recursive
- springboot
- MSA
- spring security
- 백준 19238
- Kotlin
- 백준 파이썬
- 백준 16236
- java 기술면접
- java
- 웹어플리케이션 서버
- spring oauth
- 파이썬
- JVM
- MySQL
- re.split
- 프로그래머스
- spring cloud
- Coroutine
- JPA
- Spring Boot
Archives
- Today
- Total
시작이 반
[백준] 16234번 (python 파이썬) 본문
SMALL
구현, BFS 문제이다.
처음에 문제를 이해했을 때 하루동안 2지역에서 인구이동이 일어났으면 2번 인구가 이동했을거라고 생각하고 풀었다.
이게아니라
하루에 여러곳에서 인구가 이동했다고 해도 한번으로 인구이동이 발생했다고 친다.
하루에 이렇게 주황구역, 파란구역에서 인구 이동이 일어났으면 2번 발생한게 아니라 한번으로 친다. -> 하루에 한번이라도 어떤 구역에서 인구이동이 발생하면 한번으로 친다.
0,0 에서부터 bfs를 돌리고 n,n까지 돌린뒤 인구 이동이 발생했는치 체크하고
발생했으면 다시 0,0부터 bfs를 돌린다.
이동이 발생하지 않으면 무한루프를 멈춘다.
from collections import deque
n, l, r = map(int, input().split(' '))
graph = [list(map(int, input().split(' '))) for _ in range(n)]
d_x = [-1, 0, 1, 0]
d_y = [0, 1, 0, -1]
is_move = False
def bfs(c_x, c_y, visited, grpah):
global is_move
people = graph[c_x][c_y]
count = 1
queue = deque()
queue.append((c_x, c_y))
visited[c_x][c_y] = True
temp = list()
temp.append((c_x, c_y))
while queue:
pop_x, pop_y = queue.popleft()
for i in range(4):
n_x = pop_x + d_x[i]
n_y = pop_y + d_y[i]
if n_x < 0 or n_x >= n or n_y < 0 or n_y >= n:
continue
if visited[n_x][n_y]:
continue
if l <= abs(grpah[pop_x][pop_y] - grpah[n_x][n_y]) <= r:
visited[n_x][n_y] = True
queue.append((n_x, n_y))
people += graph[n_x][n_y]
count += 1
temp.append((n_x, n_y))
move_people = people // count
if count > 1:
is_move = True
for x, y in temp:
graph[x][y] = move_people
answer = 0
while True:
is_move = False
visited = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs(i, j, visited, graph)
if is_move:
answer += 1
else:
break
print(answer)
LIST
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 20056번 (python 파이썬) (0) | 2021.04.09 |
---|---|
[백준] 16719번 (python 파이썬) (0) | 2021.04.08 |
[백준] 16719번 (python 파이썬) (2) | 2021.04.07 |
[백준] 14719번 (python 파이썬) (0) | 2021.04.06 |
[백준] 20164번 (python 파이썬) (0) | 2021.04.05 |