인구 이동
백준 16234: https://www.acmicpc.net/problem/16234
Edge case
1. 문제조건
1 day 안에서 여러 구역으로 나눠서 각각 따로따로 average를 구해야하는거였는데
- 그냥 1day에 모든 구역들의
모든 인구 / 모든 블록 수
로 계산해버림
- 그냥 1day에 모든 구역들의
Code
1트: fail
2트: 6936ms (python3)
3트: 4276ms (python3)
4트: 376ms (python3)
1. 1트 (FAIL)
FAIL
- 여러 구역으로 나뉘는걸 생각하지 못하고, 한번에 모든 구역들을 통합해서 다 average를 구해버림
# 인구 이동
# 백준 16234
# https://www.acmicpc.net/problem/16234
# 18:52 - 19:52 FAIL
from collections import deque
N, L, R = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
check = [[0] * N for _ in range(N)]
open_graph = [[0] * N for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(x, y):
q = deque()
q.append((x, y))
while q:
x, y = q.popleft()
for dir in range(4):
nx, ny = x+dx[dir], y+dy[dir]
if nx < 0 or nx >= N or ny < 0 or ny >= N or open_graph[nx][ny]:
continue
if L <= abs(graph[x][y] - graph[nx][ny]) <= R:
open_graph[x][y], open_graph[nx][ny] = 1, 1
q.append((nx, ny))
def cal():
global open_graph
population = 0
cnt = 0
for x in range(N):
for y in range(N):
if open_graph[x][y] == 1:
population += graph[x][y]
cnt += 1
# 개방된 국가가 없으면 끝!
if cnt == 0:
return False
avg = population//cnt
for x in range(N):
for y in range(N):
if open_graph[x][y] == 1:
graph[x][y] = avg
# open_graph 초기화!
open_graph = [[0] * N for _ in range(N)]
return True
if __name__ == "__main__":
day = 0
while True:
flag = False
check = [[0] * N for _ in range(N)]
for x in range(N):
for y in range(N):
if not check[x][y]:
check[x][y] = 1
bfs(x, y) # 이렇게 가야할지 아니면 열린곳을 ㅗ타고타고 해서 가야할지 모르겠네
if cal():
flag = True
if not flag:
break
else:
day += 1
print(day)
2. 2트
6936ms (Python3)
- solution함수안의 cals 배열 초기화 위치 실수 (while문 안에 있었어야 했는데 꺼내놓고있었음)
- tmp에 x, y를 기본적으로 추가하고 이걸 cals에 추가하게되면 밑의
if not len(cals)
구문에서 무조건 지나치는 문제 발생
from collections import deque
N, L, R = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
check = [[0]*N for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(x, y, check):
q = deque()
q.append((x, y))
cal = list()
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx < 0 or nx >= N or ny < 0 or ny >= N:
continue
if check[nx][ny]:
continue
if L <= abs(graph[x][y] - graph[nx][ny]) <= R:
q.append((nx, ny))
cal.append((nx, ny))
check[nx][ny] = 1
return cal
def solution():
day = 0
while True:
flag = False
cals = list()
tmpx = list()
check = [[0]*N for _ in range(N)]
for x in range(N):
for y in range(N):
if not check[x][y]:
check[x][y] = 1
tmp = bfs(x, y, check)
if tmp:
tmpx.append(tmp)
tmp.append((x, y))
cals.append(tmp)
if not len(cals):
return day
for cs in cals:
sum = 0
for x, y in cs:
sum += graph[x][y]
avg = sum // len(cs)
for x, y in cs:
graph[x][y] = avg
day += 1
if __name__ == "__main__":
print(solution())
3. 3트
4276ms (python3)
어차피 한번 검사할때 상하좌우를 이미 보니깐 다음번엔 상하좌우는 피해서 검사해도 됨
for x in range(N): for y in range(x%2, N, 2):
- 평균 계산하는것도 bfs 함수실행시 한번에 하게하여, 코드 가독성 향상
# 인구 이동
# 백준 16234
# https://www.acmicpc.net/problem/16234
# 14:25 -
# avg 대입과정 최적화
# 찾는 범위를 벽돌쌓듯 진행
from collections import deque
N, L, R = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
check = [[0]*N for _ in range(N)]
flag = False
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(x, y, check):
global flag
q = deque()
q.append((x, y))
cal_list = [(x, y)]
sum = graph[x][y]
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx < 0 or nx >= N or ny < 0 or ny >= N:
continue
if check[nx][ny]:
continue
if L <= abs(graph[x][y] - graph[nx][ny]) <= R:
q.append((nx, ny))
cal_list.append((nx, ny))
sum += graph[nx][ny]
check[nx][ny] = 1
if len(cal_list) > 1:
flag = True
avg = sum // len(cal_list)
for x, y in cal_list:
graph[x][y] = avg
def solution():
day = 0
global flag
while True:
flag = False
cal_list = list()
check = [[0]*N for _ in range(N)]
for x in range(N):
for y in range(x%2, N, 2):
if not check[x][y]:
check[x][y] = 1
bfs(x, y, check)
if not flag:
return day
day += 1
if __name__ == "__main__":
print(solution())
4. 4트
376ms (python3)
- 전날에 값을 변경한 곳 근처만 조사하도록 변경
# 인구 이동
# 백준 16234
# https://www.acmicpc.net/problem/16234
# 14:25 -
# avg 대입과정 최적화
# 찾는 범위를 벽돌쌓듯 진행
# 전날에 값을 변경한 근처만 조사할수있도록 변경
from collections import deque
N, L, R = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
check = [[0]*N for _ in range(N)]
flag = False
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(x, y, check, pos_tmp):
global flag
q = deque()
q.append((x, y))
cal_list = [(x, y)]
sum = graph[x][y]
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx < 0 or nx >= N or ny < 0 or ny >= N:
continue
if check[nx][ny]:
continue
if L <= abs(graph[x][y] - graph[nx][ny]) <= R:
q.append((nx, ny))
cal_list.append((nx, ny))
sum += graph[nx][ny]
check[nx][ny] = 1
if len(cal_list) > 1:
flag = True
avg = sum // len(cal_list)
for x, y in cal_list:
graph[x][y] = avg
pos_tmp.append((x, y))
def solution():
day = 0
global flag
pos = [(x, y) for x in range(N) for y in range(x%2, N, 2)]
while True:
flag = False
pos_tmp = list()
check = [[0]*N for _ in range(N)]
for x, y in pos:
if not check[x][y]:
check[x][y] = 1
bfs(x, y, check, pos_tmp)
if not flag:
return day
day += 1
pos = pos_tmp
if __name__ == "__main__":
print(solution())
반응형
'코딩테스트' 카테고리의 다른 글
국영수 Python 정리 및 구현 (백준 10825) (2) | 2022.09.02 |
---|---|
블록 이동하기 Python 정리 및 구현 (카카오 기출 / 프로그래머스) (3) | 2022.09.02 |
감시 피하기 Python 정리 및 구현 (백준 18428) (0) | 2022.08.30 |
연산자 끼워넣기 Python 정리 및 구현 (백준 14888, 삼성 SW 역량테스트) (0) | 2022.08.30 |
괄호변환 Python 정리 및 분석 (프로그래머스, 카카오 기출) (0) | 2022.07.29 |
댓글