백준 #16234 - [G5] 인구 이동 : 그래프탐색, 그룹핑

(python3)

16234번: 인구 이동

 

DFS로 그룹 지어주기, 재귀 최대 깊이 설정

open_border() 에서는 모든 칸들에 대해 DFS 를 수행해서 그룹을 만들어줍니다. 이미 그룹이 정해진 노드는 DFS 를 수행할 필요가 없으므로 넘어갑니다.

population_move(g) 에서는 최대 그룹 번호를 넣어서 dict 의 초기 세팅을 진행합니다. dict에는 그룹마다 총 인구수, 포함되는 나라 수, 나라의 좌표를 저장합니다.

dict 를 완성한 뒤, dict 에 저장된 정보에 따라 인구수를 모두 새로 배당해줍니다.

재귀로 DFS 를 구현했기 때문에 재귀 최대 깊이를 늘려줄 필요가 있습니다.

 

코드

import sys
sys.setrecursionlimit(100000)
def solution(input) :
    N,L,R = list(map(int,input().split()))
    population_map = []
    for _ in range(N) :
        population_map.append(list(map(int,input().split())))
    D = [(-1,0),(1,0),(0,-1),(0,1)]

    def dfs(r,c,g) :
        if visit[r][c] : # 들른적 있으면
            return
        visit[r][c] = g
        for dr,dc in D :
            nr = r+dr
            nc = c+dc
            if nr>=0 and nr<N and nc>=0 and nc<N and abs(population_map[r][c]-population_map[nr][nc]) >= L and  abs(population_map[r][c]-population_map[nr][nc]) <= R:
                dfs(nr,nc,g)

    def open_border() :
        g = 0
        for r in range(N) :
            for c in range(N) :
                if visit[r][c] :
                    continue
                else :
                    g+=1
                    dfs(r,c,g)
        if g == N*N : # 경계가 하나도 안열린경우
            return -1
        else :
            return g
    
    def population_move(g) :
        pop_dict = {
            gn : {
                'pop_sum' : 0,
                'pop_count' : 0,
                'points' : []
            }
            for gn in range(1,g+1)
        }

        for r in range(N) :
            for c in range(N) :
                g = visit[r][c]
                pop_dict[g]['pop_sum'] += population_map[r][c]
                pop_dict[g]['pop_count'] += 1
                pop_dict[g]['points'].append((r,c))

        for gn in pop_dict :
            n_pop = pop_dict[gn]['pop_sum'] // pop_dict[gn]['pop_count']
            for r,c in pop_dict[gn]['points'] :
                population_map[r][c] = n_pop

    cnt = 0
    while True :
        visit = [[0 for _ in range(N)] for _ in range(N)]
        g = open_border()
        if g == -1 :
            print(cnt)
            return
        else :
            cnt+=1
            population_move(g)

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac