인구 이동 Python 정리 및 구현 (백준 16234, 삼성 SW 역량테스트)

인구 이동

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

Edge case

1. 문제조건

• 1 day 안에서 여러 구역으로 나눠서 각각 따로따로 average를 구해야하는거였는데

  • 그냥 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())