인구 이동 - BOJ 16234 삼성전자 SW 역량테스트
in ALGORITHM
‘풀이시간 40분 , 시간제한 2초, 메모리제한 512MB, BOJ 16234 삼성전자 SW 역량테스트 (취코테 353p)’
인구 이동 - BOJ 16234
BFS를 활용하여 인접한 지역이 연합이 가능한 국가인지 확인을 하고 연합하고 인구를 이동하는 과정을 거쳐야 한다.
이번에 알았는데 파이썬은 한줄로 ~이상 ~이하를 and 없이 한번에 적용할수 있었다.
여기서 union 리스트는 visited 리스트와 같은 역할을 한다고 생각하면 된다. 방문 여부를 체크하는 것이다.
그래프 전체를 돌면서 연합들을 만들어 주고 모든 연합들의 인구를 이동시키면 인구 이동 횟수 total_count를 1 증가 시키면 된다. 결국 마지막에 인구이동을 할수 없을때까지 가면 연합의 수가 전체 국가의 수가 되므로 그때 반복문을 종료하도록 설정하면 된다.
참고로 해당 코드는 python3로 돌리면 시간초과 뜨므로 pypy로 돌려주면 된다…
from collections import deque
# 땅의 크기(N), L, R 값을 입력받기
n, l, r = map(int, input().split())
# 전체 나라의 정보(N x N)를 입력 받기
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
# 특정 위치에서 출발하여 모든 연합을 체크한 뒤에 데이터 갱신
def process(x, y, index):
# (x, y)의 위치와 연결된 나라(연합) 정보를 담는 리스트
united = []
united.append((x, y))
# 너비 우선 탐색 (BFS)을 위한 큐 라이브러리 사용
q = deque()
q.append((x, y))
union[x][y] = index # 현재 연합의 번호 할당
summary = graph[x][y] # 현재 연합의 전체 인구 수
count = 1 # 현재 연합의 국가 수
# 큐가 빌 때까지 반복(BFS)
while q:
x, y = q.popleft()
# 현재 위치에서 4가지 방향을 확인하며
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 바로 옆에 있는 나라를 확인하여
if 0 <= nx < n and 0 <= ny < n and union[nx][ny] == -1: # 범위를 벗어나지 않고 방문한적이 없다면
# 옆에 있는 나라와 인구 차이가 L명 이상, R명 이하라면
if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
q.append((nx, ny))
# 연합에 추가하기
union[nx][ny] = index
summary += graph[nx][ny]
count += 1
united.append((nx, ny))
# 연합 국가끼리 인구를 분배
for i, j in united:
graph[i][j] = summary // count
total_count = 0
# 더 이상 인구 이동을 할 수 없을 때까지 반복
while True:
union = [[-1] * n for _ in range(n)] # 나라의 정보 처리여부 저장 (방문 체크용, 매 반복마다 -1로 초기화됨)
index = 0
for i in range(n):
for j in range(n):
if union[i][j] == -1: # 해당 나라가 아직 처리되지 않았다면
process(i, j, index)
index += 1
# 모든 인구 이동이 끝난 경우
if index == n * n:
break
total_count += 1
# 인구 이동 횟수 출력
print(total_count)
