[ BOJ / Python ] 16234번 인구 이동
이번 문제는 삼성 기출 문제로 BFS를 통해 개방할 수 있는 국경선들을 모두 체크하고, 현재 위치의 나라와 연결된 모든 나라들을 구하여 그 나라들의 인구수를 평균값으로 갱신해준다. 이 과정을 거치기 전의 전체 나라들의 인구 상황을 저장하고, 이 과정을 거친 후의 인구 상황과 비교하여 둘이 같을 때가지 반복하여 진행하였다.
- n, l, r을 입력받는다.
- ground를 입력받는다.
- dy, dx에 4가지 방향을 저장한다.
- bfs함수를 sy, sx를 인자로 갖도록 선언한다.
-> q를 deque로 선언한다.
-> q에(sy, sx)
를 넣는다.
->visited[sy][sx]
를 1로 갱신한다.
-> 연결된 나라들의 인구수를 저장할 변수 total을ground[sy][sx]
로 선언한다.
-> 연결된 나라들의 위치를 저장할 리스트 cnt를 선언하고 (sy, sx)를 넣는다.
-> q가 존재할 동안 반복하는 while문을 돌린다.
--> q에서 y, x를 추출한다.
--> 4번 반복하는 i에 대한 for문을 돌린다.
---> ny, nx를y+dy[i]
,x+dx[i]
로 선언한다.
---> 만약 ny, nx가 0 이상, n 미만이고,visited[ny][nx]
가 0이고,ground[y][x]-ground[ny][nx]
의 절댓값이 l 이상, r 이하일 경우,
---->visited[ny][nx]
를 1로 갱신한다.
----> total에ground[ny][nx]
를 더한다.
----> cnt에(ny, nx)
를 넣는다.
----> q에(ny, nx)
를 넣는다.
-> cnt를 순회하는 i, j에 대한 for문을 돌린다.
-->ground[i][j]
를total//len(cnt)
로 갱신한다. - answer를 0으로 선언한다.
- 계속 반복하는 while문을 돌린다.
-> tmp에 ground를 deepcopy하여 저장한다.
-> 방문처리 리스트 visited를n*n
크기로 선언하고 0으로 채운다.
-> n번 반복하는 i에 대한 for문을 돌린다.
--> n번 반복하는 j에 대한 for문을 돌린다.
---> 만약visited[i][j]
가 0일 경우,
---->bfs(i, j)
를 호출한다.
-> 만약 tmp가 ground와 다를 경우,
--> answer를 1 증가시킨다.
-> 그 외의 경우,
--> while문을 탈출한다. - answer를 출력한다.
Code
from collections import deque
from copy import deepcopy
n, l, r=map(int, input().split())
ground=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[1, 0, -1, 0], [0, 1, 0, -1]
def bfs(sy, sx):
q=deque()
q.append((sy, sx))
visited[sy][sx]=1
total=ground[sy][sx]
cnt=[(sy, sx)]
while q:
y, x=q.popleft()
for i in range(4):
ny, nx=y+dy[i], x+dx[i]
if 0<=ny<n and 0<=nx<n and not visited[ny][nx] and l<=abs(ground[y][x]-ground[ny][nx])<=r:
visited[ny][nx]=1
total+=ground[ny][nx]
cnt.append((ny, nx))
q.append((ny, nx))
for i, j in cnt:
ground[i][j]=total//len(cnt)
answer=0
while True:
tmp=deepcopy(ground)
visited = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs(i, j)
if tmp!=ground:
answer+=1
else:
break
print(answer)
from collections import deque
from copy import deepcopy
n, l, r=map(int, input().split())
ground=[list(map(int, input().split())) for _ in range(n)]
dy, dx=[1, 0, -1, 0], [0, 1, 0, -1]
def bfs(sy, sx):
q=deque()
q.append((sy, sx))
visited[sy][sx]=1
total=ground[sy][sx]
cnt=[(sy, sx)]
while q:
y, x=q.popleft()
for i in range(4):
ny, nx=y+dy[i], x+dx[i]
if 0<=ny<n and 0<=nx<n and not visited[ny][nx] and l<=abs(ground[y][x]-ground[ny][nx])<=r:
visited[ny][nx]=1
total+=ground[ny][nx]
cnt.append((ny, nx))
q.append((ny, nx))
for i, j in cnt:
ground[i][j]=total//len(cnt)
answer=0
while True:
tmp=deepcopy(ground)
visited = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs(i, j)
if tmp!=ground:
answer+=1
else:
break
print(answer)
Author And Source
이 문제에 관하여([ BOJ / Python ] 16234번 인구 이동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-16234번-인구-이동저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)