[python] 16234 - 인구 이동

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

정답률 36.050%

난이도 골5

80%에서 시간초과 오지게 남.. 최적화된 bfs가 필요

 

---

코드 설명

1. 입력 받기

2. bfs

3. 그룹 생성되면 인구 이동

 

 

※ 주의할 점

• 처음 검사할 때 모든 칸을 다 조사할 필요 x
  한 점에서 사방으로 관계를 조사하기 때문에 격자로 검사 
• 두번째 날부터는 전날 그룹생성되었던 점들만 검사(숫자 바뀐 부분만 검사하면 되니까)
• visited에 date를 넣어두면 할때마다 초기화 안해줘도 됨

from collections import deque
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

# 2. bfs
def bfs(sx, sy):
    temp = [(sx, sy)]
    cnt = board[sx][sy]
    num = 1
    for x, y in temp: # 뒤에서 append되는 애들도 적용됨
        v = board[x][y]
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if nx == -1 or nx == N or ny == -1 or ny == N:
                continue
            if visited[nx][ny] == date:
                continue
            diff = abs(v - board[nx][ny])
            if L <= diff <= R:
                temp.append((nx, ny))
                cnt += board[nx][ny]
                visited[nx][ny] = date
                num += 1
    return temp, cnt, num

# 1. 입력 받기
N, L, R = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
q = deque((x, y) for x in range(N) for y in range(x % 2, N, 2)) # 격자로만 검사
visited = [[-1] * N for _ in range(N)]


date = 0
while q:
    # 처음 돌때는 입력받은 보드에서 격자로 추출한 모든 점 검사
    # 그다음 날짜부터는 이전 날짜에서 그룹 내에 속해있던 점만 검사(숫자 바뀐애들만 다시 검사하면 되니까)
    for _ in range(len(q)):
        x, y = q.popleft()
        if visited[x][y] == date:
            continue
        visited[x][y] = date
        g, c, n = bfs(x, y)

        # 3. 그룹 생성되면 인구 이동
        if n > 1:
            div = c//n
            for nx, ny in g:
                board[nx][ny] = div
                q.append((nx, ny))
    
    date += 1


print(date - 1)

 

---

코드 결과