16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
문제
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
- 연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.
출력
인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.
풀이
사실 이 문제 이해만 하는데 한참 걸렸다 😭
말로 설명하는 것보다 그림으로 보는 것이 더 직관적으로 이해할 수 있을 것이다.
예제 5를 풀어보면 다음과 같이 인구 이동이 3일 걸린다는 것을 알 수 있다.
답안 코드
나는 깊이우선탐색(DFS), 재귀함수를 이용해서 구현하여 풀었는데, 런타임에러에서 조금 애를 먹었다..
런타임 에러
언어: C99, C11, C90, C2x, C++98, C++11, C++14, C++17, C++20 런타임 에러 이유설명AssertionFailedassert함수가 실패SegfaultSegmentation faultBusErrorBus errorInvalidPointermunmap_chunk(): invalid pointerOutOfBounds컨테이너 또는 배열
help.acmicpc.net
백준 채점에서 파이썬 런타임 에러 이유들을 보니, RecursionError가 있었다.
재귀함수를 사용해서 확인해보니...
가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때입니다.
해결 방법은 재귀 함수를 사용하지 않거나, sys.setrecursionlimit()을 사용해서 최대 재귀 깊이를 변경하는 것!
두 번째 방법을 사용해서 제출하니 성공했다.
## 재귀함수 풀이
import sys
sys.setrecursionlimit(10**6)
from collections import deque
input = sys.stdin.readline
answer =0
N, L, R = map(int, input().split())
A = []
for _ in range (N):
A.append(list(map(int, input().split())))
def func1(i,j,united):
visited[i][j] = True
united.append([i,j])
if j < N-1 and L<=abs(A[i][j] - A[i][j+1]) <=R:
if not visited[i][j+1]:
func1(i,j+1,united)
if i < N-1 and L<=abs(A[i][j] - A[i+1][j]) <=R:
if not visited[i+1][j]:
func1(i+1,j,united)
if j > 0 and L<=abs(A[i][j] - A[i][j-1]) <=R:
if not visited[i][j-1]:
func1(i,j-1,united)
if i > 0 and L<=abs(A[i][j] - A[i-1][j]) <=R:
if not visited[i-1][j]:
func1(i-1,j,united)
while True:
visited = [[False]*51 for i in range(51)]
countries=[]
for i in range(N):
for j in range(N):
united=[]
if not visited[i][j]:
func1(i,j,united)
if united:
countries.append(united)
if len(countries) == N*N:
break
answer+=1
for united in countries:
if len(united) > 1:
# calculate new population
new_p=0
for (i,j) in united:
new_p += A[i][j]
new_p=new_p//len(united)
# update new population
for (i,j) in united:
A[i][j] = new_p
print(answer)
근데...
알고리즘 분류와 다른 사람들의 풀이를 보니 BFS로 접근하면 더 빠를수 있다는 것을 깨달았다.
+ 특히 2차원 배열 공간에서 이동하는 건 move_x, move_y로 설정해서 풀면 깔끔하게 가능!
하지만 또 다른 문제가 있었으니... 바로 시간초과...
해결방법은 생각보다 간단한데,
Python3말고 Pypy3로 제출하면 해결된다.
이유는... 설명해주는 블로그가 많으니 찾아보자!!
## BFS 풀이
import sys
from collections import deque
input = sys.stdin.readline
moves_x=[-1, 0, 1, 0]
moves_y=[0, -1, 0, 1]
answer =0
N, L, R = map(int, input().split())
A = []
for _ in range (N):
A.append(list(map(int, input().split())))
def bfs(x,y):
visited[x][y]=True
united=[[x,y]]
queue=deque([[x,y]])
while queue:
x,y = queue.popleft()
for mx, my in zip(moves_x, moves_y):
new_x, new_y = x+mx, y+my
if 0<=new_x<N and 0<=new_y<N:
if not visited[new_x][new_y] and L<=abs(A[x][y]-A[new_x][new_y])<=R:
visited[new_x][new_y] = True
united.append([new_x, new_y])
queue.append([new_x, new_y])
return united
while True:
visited = [[False]*N for i in range(N)]
countries=[]
for x in range(N):
for y in range(N):
if not visited[x][y]:
countries.append(bfs(x,y))
if len(countries) == N*N: break
else: answer+=1
for united in countries:
if len(united) > 1:
# calculate new population
new_p=0
for (i,j) in united:
new_p += A[i][j]
new_p=new_p//len(united)
# update new population
for (i,j) in united:
A[i][j] = new_p
'Algorithm' 카테고리의 다른 글
[백준] 16235번: 나무 재테크- 파이썬 (0) | 2022.01.22 |
---|---|
[백준] 17780번: 새로운 게임 - 파이썬 (0) | 2022.01.20 |
[백준] 2003번: 수들의 합 2 -파이썬 (0) | 2022.01.13 |
[백준] 1697번: 숨바꼭질 -파이썬 (0) | 2022.01.13 |
[백준] 10845번: 큐 -파이썬 (1) | 2022.01.11 |