[백준] 16234번 인구 이동
문제 링크
https://www.acmicpc.net/problem/16234
문제 설명
- 인접한 좌표 간 인구가 일정 범위 안에 있는 것들끼리 평균 값으로 인구 이동
- 이동 횟수 출력
풀이
- DFS로 연합마다 번호를 매김
- 각 연합에 해당하는 값을 평균 값으로 갱신
- 연합이 생기지 않을 때까지 반복
느낀 점
- 알고리즘이 어려운건 없었던 것 같다
코드
def init():
import sys
ipt = sys.stdin.readline
n, l, r = map(int, ipt().split())
board = []
for _ in range(n):
row = list(map(int, ipt().split()))
board.append(row)
dx = [1,-1,0,0]
dy = [0,0,1,-1]
return n, l, r, board, 0, dx, dy
def dfs(start):
sy, sx = start
union[sy][sx] = num
sum_list[num][0] += board[sy][sx]
sum_list[num][1] += 1
for i in range(4):
ny = sy + dy[i]
nx = sx + dx[i]
if 0 <= ny < n and 0 <= nx < n:
if not union[ny][nx]:
if l <= abs(board[ny][nx] - board[sy][sx]) <= r:
dfs((ny, nx))
def move():
for i in range(n):
for j in range(n):
board[i][j] = sum_list[union[i][j]][0] // sum_list[union[i][j]][1]
n, l, r, board, count, dx, dy = init()
while True:
num = 1
union = [[0] * n for _ in range(n)]
sum_list = [[0, 0] for _ in range(n**2+1)]
for i in range(n):
for j in range(n):
if not union[i][j]:
dfs((i, j))
num += 1
if union[-1][-1] == n**2:
break
move()
count += 1
print(count)
Author And Source
이 문제에 관하여([백준] 16234번 인구 이동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-16234번-인구-이동
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- DFS로 연합마다 번호를 매김
- 각 연합에 해당하는 값을 평균 값으로 갱신
- 연합이 생기지 않을 때까지 반복
느낀 점
- 알고리즘이 어려운건 없었던 것 같다
코드
def init():
import sys
ipt = sys.stdin.readline
n, l, r = map(int, ipt().split())
board = []
for _ in range(n):
row = list(map(int, ipt().split()))
board.append(row)
dx = [1,-1,0,0]
dy = [0,0,1,-1]
return n, l, r, board, 0, dx, dy
def dfs(start):
sy, sx = start
union[sy][sx] = num
sum_list[num][0] += board[sy][sx]
sum_list[num][1] += 1
for i in range(4):
ny = sy + dy[i]
nx = sx + dx[i]
if 0 <= ny < n and 0 <= nx < n:
if not union[ny][nx]:
if l <= abs(board[ny][nx] - board[sy][sx]) <= r:
dfs((ny, nx))
def move():
for i in range(n):
for j in range(n):
board[i][j] = sum_list[union[i][j]][0] // sum_list[union[i][j]][1]
n, l, r, board, count, dx, dy = init()
while True:
num = 1
union = [[0] * n for _ in range(n)]
sum_list = [[0, 0] for _ in range(n**2+1)]
for i in range(n):
for j in range(n):
if not union[i][j]:
dfs((i, j))
num += 1
if union[-1][-1] == n**2:
break
move()
count += 1
print(count)
Author And Source
이 문제에 관하여([백준] 16234번 인구 이동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-16234번-인구-이동
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def init():
import sys
ipt = sys.stdin.readline
n, l, r = map(int, ipt().split())
board = []
for _ in range(n):
row = list(map(int, ipt().split()))
board.append(row)
dx = [1,-1,0,0]
dy = [0,0,1,-1]
return n, l, r, board, 0, dx, dy
def dfs(start):
sy, sx = start
union[sy][sx] = num
sum_list[num][0] += board[sy][sx]
sum_list[num][1] += 1
for i in range(4):
ny = sy + dy[i]
nx = sx + dx[i]
if 0 <= ny < n and 0 <= nx < n:
if not union[ny][nx]:
if l <= abs(board[ny][nx] - board[sy][sx]) <= r:
dfs((ny, nx))
def move():
for i in range(n):
for j in range(n):
board[i][j] = sum_list[union[i][j]][0] // sum_list[union[i][j]][1]
n, l, r, board, count, dx, dy = init()
while True:
num = 1
union = [[0] * n for _ in range(n)]
sum_list = [[0, 0] for _ in range(n**2+1)]
for i in range(n):
for j in range(n):
if not union[i][j]:
dfs((i, j))
num += 1
if union[-1][-1] == n**2:
break
move()
count += 1
print(count)
Author And Source
이 문제에 관하여([백준] 16234번 인구 이동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-16234번-인구-이동저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)