문제
https://www.acmicpc.net/problem/16234
전략
Python에서 메모리 초과, 시간 초과 문제 해결에 오래 걸린 문제.
visited 배열의 활용 뿐만 아니라 다음 interation에서 이전에 인구 이동이 있었던 구역을 추가로 배제해주는 logic도 포함하니 AC를 받을 수 있었다.
효율적으로 한번만 돌려야했지만 중복으로 사용했던 For 문을 제거한 것도 AC에 기여했다.
접근법
1차
from collections import deque
N,L,R = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
def check(ny,nx,y,x):
"""
this 와 there 의 차이가 L 이상 R 이하인가
:return: boolean 타입으로 반환한다.
"""
global L, R
if L <= abs(arr[y][x] - arr[ny][nx]) <= R:
return True
else:
return False
def BFS(x,y)-> None:
"""
하나로 이어진 부분을 찾는다.
:return:
"""
q=deque()
q.append((x,y))
v[y][x] = 1
dy = [-1,1,0,0]
dx = [0,0,-1,1]
while q:
x, y = q.popleft()
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if ny< N and nx < N and nx >= 0 and ny >= 0 and not v[ny][nx] and check(ny,nx,y,x):
v[ny][nx] = 1
q.append((nx,ny))
flag = 0 # 아무런 값이 바뀌지 않은 것이 초기 값
tot = 0
cnt = 0
for j in range(N):
for i in range(N):
if v[j][i] == 1:
tot += arr[j][i]
cnt += 1
avg = int(tot / cnt)
for j in range(N):
for i in range(N):
if v[j][i] == 1 and arr[j][i] != avg:
arr[j][i] = avg
flag = 1
return flag
flag = 1
while flag: # 더 이상 값이 변경되지 않을 때까지 작업을 계속 해준다.
cnt = 0
ret = 0
v = [[0] * N for _ in range(N)]
for j in range(N):
for i in range(N):
if not v[j][i]: # 방문한 곳이 아니라면 BFS를 시작하자.
ret = max(BFS(i,j),ret) ## 좌상단에서부터 우측으로 BFS를 탐색하기 시작하자.
# 이 작업이 모두 끝났다면 1일차에 있는 인구이동이 마무리 되는 것이다.
flag = 1 if ret == 1 else 0
cnt += 1
print(cnt)- 모든 나라에 대해서 BFS를 수행한다. O(n)
- BFS 함수를 만들고 함수 안에서 q를 사용하여 모든 나라를 순회한다. O(n)
- 아직 visit 하지 않은 나라인데 조건을 만족하면 좌표를 담는다.
- q에 담아두었던 좌표를 순회하면서 인구를
sum에 담고cnt에 숫자를 담아서 O(n) - BFS를 종료하기 전에 인구이동에 해당하는 나라에 대해서 순회하며, 평균 인구로 인구이동으로 값을 변경한다. O(n)
문제점
- 순회를 모든 나라에 대해서 항상 BFS를 돌려야 하며, 그 안에서 다시 상하좌우를 순회.
- 인구이동을 계산하는 for 문이 두 번 중복으로 순회한다.
- 이 경우에는 시간복잡도가 O(n^4) 이 된다.
2차
- visited 배열 이외에, BFS 내부에서 초기화 되서 돌아야 하는 country 배열을 하나 더 만들었다. 그 이유는 visited로 인해서 탐색을 하지 않아서 정답이 틀린다고 생각 했기 때문.
문제점
- 이 접근은 결과적으로 틀린 접근이며 시간 복잡도를 더 늘였다. visited에 기반해서 탐색하는게 아니라 BFS 마다 초기화 되는 country 배열을 기반으로 돌면 훨씬 더 많은 순회를 해야 하는데, 이는 불필요했다.
3차
- 위에서 두 번의 순회를 통해서 인구이동을 처리하는 순회를 한 번으로 줄이고, united라는 배열을 만들어서 해당 나라에 대해서만 순회를 시킨 뒤에 그 다음 날짜의 인구이동에서는 united에 포함된 나라에 대해서 순회하지 않게 함으로써 순회 자체의 숫자를 감소 시켰다. (pyp3 성공)
4차
- Pypy3에서만 성공했는데, 그 이유는 이민하기를 BFS 바깥에서 함으로써 한번의 for문이 더 생겼기 때문. 사실 이민하기는 BFS 바깥에서 할 필요가 없고 BFS 안에서 해도 되는데, 그 이유는 visited를 사용하면 BFS 안에서 하더라도 다른 연합국에서 이전에 이민을 시킨 연합국들을 건드릴 이유가 없기 때문. country 배열을 없앰으로써 가능했다.
AC
from collections import deque
N, L, R = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
def check(ny, nx, y, x):
"""
this 와 there 의 차이가 L 이상 R 이하인가
:return: boolean 타입으로 반환한다.
"""
global L, R
if L <= abs(arr[y][x] - arr[ny][nx]) <= R:
return True
else:
return False
def BFS(x, y) -> None:
"""
하나로 이어진 부분을 찾는다.
:return:
"""
q = deque()
q.append((x, y))
united = []
v[y][x] = 1
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
tot = arr[y][x]
cnt = 1
while q:
x, y = q.popleft()
united.append([x, y]) # 연합국들을 여기에 저장해둔다. for 문 최소화하기 위해서.
# 연합국들은 다음 round에서는 조사할 필요가 없다. 연합국들은 주변국들에 의해서만 병합될 뿐이기 때문이다.
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if ny < N and nx < N and nx >= 0 and ny >= 0 and check(ny, nx, y, x) and not v[ny][nx]:
v[ny][nx] = 1
q.append((nx, ny))
tot += arr[ny][nx]
cnt += 1
flag = 0
if cnt > 1: # 연합국이 두개 이상이라면
flag = 1
avg = int(tot / cnt)
# 인구이동 여기서 시켜버림
for u in united:
x,y=u
arr[y][x] = avg
return flag
flag = 1
ans = 0
while flag:
ret = 0
v = [[0] * N for _ in range(N)]
for j in range(N):
for i in range(N):
if not v[j][i]:
ret = max(BFS(i, j), ret)
flag = 1 if ret == 1 else 0
if flag:
ans += 1
print(ans)
통계학으로 사람들의 행동을 이해하고 싶습니다.