1. 인구 이동
- 난이도
- 중
- 풀이 시간
- 40분
- 시간 제한
- 2초
- 메모리 제한
- 512 MB
- 출처
A. 문제
- 중
- 40분
- 2초
- 512 MB
위 백준 사이트에 접속하여 문제를 확인해주세요.
B. 내 답안
a. 1차 시도 (실패)
from collections import deque
N, L, R = list(map(int, input().split()))
graph = []
# diff_graph = [[0] * 4 for _ in range(N)]
diff_graph = []
for i in range(N):
graph.append(list(map(int, input().split())))
ds = ((-1, 0), (0, 1), (1, 0), (0, -1))
q = deque()
# 좌표, 시간
q.append([0, 0])
while True:
time = 0
answer = [[0] * N for _ in range(N)]
while q:
x, y = q.popleft()
for d_i in range(len(ds)):
dx = x + ds[d_i][0]
dy = y + ds[d_i][1]
if 0 <= dx < N and 0 <= dy < N:
value = abs(graph[x][y] - graph[dx][dy])
if L <= value <= R:
q.append([dx, dy])
answer[dx][dy] += 1
else:
continue
else:
continue
total_pop = 0
total_count = 0
for i in range(N):
for j in range(N):
if answer[i][j] > 0:
total_pop += graph[i][j]
total_count += 1
if total_count == 0:
break
for i in range(N):
for j in range(N):
if answer[i][j] > 0:
graph[i][j] = (total_pop // total_count)
time += 1
print(time)
# print(diff_graph)
# for i in range(N):
# for j in range(N):
# diff_list = [0] * 4
# for d_i in range(len(ds)):
# dx = i + ds[d_i][0]
# dy = j + ds[d_i][1]
#
# if 0 <= dx < N and 0 <= dy < N:
# value = abs(graph[i][j] - graph[dx][dy])
# diff_list[d_i] = value
# else:
# diff_list[d_i] = 0
# diff_graph.append(diff_list)
b. 2차 시도 ()
c. 회고
내 풀이
- 무한루프 안에 bfs를 구현하였다.
반성
- 이미 방문한 땅(국경선이 열린 땅)에 대한 체크를 어떻게 해야할지 감이 안왔다.
- 중첩 반복문 안에 다시 중첩 반복문을 만들어서 시간초과도 발생했다.
- 단순하게 중첩 반복문을 사용하기보다, 가능하다면 앞 부분에서 작성한 코드를 활용하는 방법을 생각해봐야겠다.
C. 문제 해설
이해한 내용을 바탕으로 작성했습니다.
from collections import deque
N, L, R = list(map(int, input().split()))
graph = []
# diff_graph = [[0] * 4 for _ in range(N)]
diff_graph = []
for i in range(N):
graph.append(list(map(int, input().split())))
ds = ((-1, 0), (0, 1), (1, 0), (0, -1))
q = deque()
# 좌표, 시간
q.append([0, 0])
while True:
time = 0
answer = [[0] * N for _ in range(N)]
while q:
x, y = q.popleft()
for d_i in range(len(ds)):
dx = x + ds[d_i][0]
dy = y + ds[d_i][1]
if 0 <= dx < N and 0 <= dy < N:
value = abs(graph[x][y] - graph[dx][dy])
if L <= value <= R:
q.append([dx, dy])
answer[dx][dy] += 1
else:
continue
else:
continue
total_pop = 0
total_count = 0
for i in range(N):
for j in range(N):
if answer[i][j] > 0:
total_pop += graph[i][j]
total_count += 1
if total_count == 0:
break
for i in range(N):
for j in range(N):
if answer[i][j] > 0:
graph[i][j] = (total_pop // total_count)
time += 1
print(time)
# print(diff_graph)
# for i in range(N):
# for j in range(N):
# diff_list = [0] * 4
# for d_i in range(len(ds)):
# dx = i + ds[d_i][0]
# dy = j + ds[d_i][1]
#
# if 0 <= dx < N and 0 <= dy < N:
# value = abs(graph[i][j] - graph[dx][dy])
# diff_list[d_i] = value
# else:
# diff_list[d_i] = 0
# diff_graph.append(diff_list)
b. 2차 시도 ()
c. 회고
내 풀이
- 무한루프 안에 bfs를 구현하였다.
반성
- 이미 방문한 땅(국경선이 열린 땅)에 대한 체크를 어떻게 해야할지 감이 안왔다.
- 중첩 반복문 안에 다시 중첩 반복문을 만들어서 시간초과도 발생했다.
- 단순하게 중첩 반복문을 사용하기보다, 가능하다면 앞 부분에서 작성한 코드를 활용하는 방법을 생각해봐야겠다.
C. 문제 해설
이해한 내용을 바탕으로 작성했습니다.
내 풀이
- 무한루프 안에 bfs를 구현하였다.
반성
- 이미 방문한 땅(국경선이 열린 땅)에 대한 체크를 어떻게 해야할지 감이 안왔다.
- 중첩 반복문 안에 다시 중첩 반복문을 만들어서 시간초과도 발생했다.
- 단순하게 중첩 반복문을 사용하기보다, 가능하다면 앞 부분에서 작성한 코드를 활용하는 방법을 생각해봐야겠다.
C. 문제 해설
이해한 내용을 바탕으로 작성했습니다.
이해한 내용을 바탕으로 작성했습니다.
예제 4번과 5번에 대한 풀이는 다음과 같다.
- 모든 땅에 방문한다.
- 연산의 반복을 방지하기 위해 방문한 땅은 체크한다.
- 4방향(상하좌우)를 확인하고 조건(두 나라의 인구 차이가 L명 이상, R명 이하)을 만족하면 조건을 만족하지 않을때까지 bfs를 반복한다.
- 방문한 땅으로 체크한다.
- 확인한 땅을 bfs q에 집어넣는다.
- bfs q가 끝나면(조건을 만족하는 나라끼리 국경선을 다 열었으면) 인구 이동을 시작한다.
- 1번으로 돌아가서 모든 땅을 방문할 때까지(방문한 땅이 전부 체크될 때까지)반복한다.
bfs쪽에서 인구이동할 도시를 2중 for문으로 찾으면 시간초과가 발생한다.
for i in range(N):
for j in range(N):
if check[i][j] == group_num:
graph[i][j] = result // go_count
a. 책 답안
python-for-coding-test/7.py at master · ndb796/python-for-coding-test (github.com)
참고문헌
[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년
[2] 16234번: 인구 이동 (acmicpc.net). Baekjoon. (accessed Sep 28, 2021)
Ghost