[Python] 16234. 인구 이동

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

16234번: 인구 이동

 

접근법

• 각 나라를 돌면서 인접한 나라와의 인구 차를 계산하고, L이상 R이하라면 union_country에 추가 -> bfs 활용
• union_country에 있는 국가들로 인구수를 업데이트 함.
• 더 이상 인구이동이 없을 때까지 반복 -> flag변수를 활용

from collections import deque

def init_func(N):
    arr = []
    for i in range(N):
        arr.append(list(map(int, input().split())))
    return arr

def bfs(x, y, L, R):
    """
    :param x: 현재 위치 x
    :param y: 현재 위치 y
    :param L, R: L 이상 R이하의 인구수 차이라면 Union
    :return:
    """
    # 인접한 나라의 위치
    d = [(1,0), (0,1), (-1, 0), (0,-1)]
    q = deque()
    N = len(arr)
    union_country = []
    # 현재 위치를 q와 union_country에 추가
    q.append((x,y))
    union_country.append((x,y))
    
    while q:
        x,y = q.popleft()
        for move_x, move_y in d:
            nx = x + move_x
            ny = y + move_y
            if (0 <= nx < N) and (0 <= ny < N) and not (visited[nx][ny]):
                if L <= abs(arr[x][y] - arr[nx][ny]) <= R:
                    visited[nx][ny] = True
                    q.append((nx,ny))
                    union_country.append((nx,ny))
    return union_country

def solution(N, L, R):
    answer = 0
    while True:
        global visited
        visited = [[0]*N for _ in range(N)]
        move = False
        for i in range(N):
            for j in range(N):
                if not visited[i][j]:
                    visited[i][j] = True
                    union_country = bfs(i, j, L, R)
                    if 1 < len(union_country):
                        move = True
                        population = sum([arr[x][y] for x, y in union_country]) // len(union_country)
                        for x, y in union_country:
                            arr[x][y] = population
        # 인구 이동이 일어나지 않은 경우
        if not move:
            break
        # 인구이동이 일어난 경우
        else:
            answer += 1
    print(answer)

def main():
    N, L, R = map(int, input().split())
    global arr
    arr = init_func(N)
    solution(N, L, R)

if __name__=="__main__":
    main()

---

처음 생각했던 알고리즘의 문제점(틀린이유)

try1

(1) find_neighbor함수에서 candidate_list에 모든 후보 리스트를 넣지 않은듯.

from collections import deque
def find_neighbor(map_arr, cur, min, max, visited):
    neighbor_list = []
    neighbor_total = 0
    while cur:
        cur_x, cur_y = cur.popleft()
        candidate_list = [[cur_x+1, cur_y], [cur_x,cur_y+1]]
        for can_x, can_y in candidate_list:
            if (can_x >= len(map_arr)) or (can_y >= len(map_arr)):
                continue
            if visited[can_x][can_y] == 1:
                continue
            diff = abs(map_arr[cur_x][cur_y] - map_arr[can_x][can_y])
            if (diff >= min) and (diff <= max):
                visited[can_x][can_y] = 1
                neighbor_list.append([can_x, can_y])
                neighbor_total += map_arr[can_x][can_y]
                cur.append([can_x, can_y])
    return neighbor_list, neighbor_total

def count_days(map_arr,L, R):
    # 재귀로 연결된 모든 이웃들을 찾아야 함.
    day = 0
    # while(True):
    visited = [[0 for j in range(len(map_arr))] for i in range(len(map_arr))]
    nation_list = deque()
    nation_list.append([0,0])
    visited[0][0] = 1
    while(nation_list):
        for i in range(len(map_arr)):
            for j in range(len(map_arr)):
                neighbor, neighbor_total = find_neighbor(map_arr, nation_list, L, R, visited)
                neighbor.append([i,j])
                # print("current : ", (i, j), "neighbor : ", neighbor)
                for nation_x, nation_y in neighbor:
                    map_arr[nation_x][nation_y] = neighbor_total/len(neighbor)
        day += 1
    return day

def input_arr(N):
    arr = []
    for i in range(N):
        arr_tmp = list((map(int, input().split())))
        arr.append(arr_tmp)
    return arr

def main():
    N, L, R = map(int, input().split())
    map_arr = input_arr(N)
    result = count_days(map_arr, L, R)
    print(result)

if __name__ == "__main__":
    main()

사용된 알고리즘

구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시뮬레이션