[#16234] 인구이동

 

 

 

백준 16234 인구이동 (브론즈)

16234번: 인구 이동

 

분기가 까다로운 시뮬레이션 -> 쉽다고 대충손만 놀리다가 더 귀찮아짐
+ BFS로 영역찾기 

 

처음 문제를 읽고

시뮬레이션이라서 크게 어떤 함수가 어디에 어떻게 쓰일것인지 구상해봤다.

# 데이터 입력받기
N, L, R = map(int, input().split())
graph = []
for _ in range(N) : 
    graph.append(list(map(int, input().split())))




dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
visited = [[0]*N for _ in range(N)]
visted_cnt = 1
# 연합이 될 수 있는 국가를 visited 그래프에 1,2,3,4... 연합국등으로 체크하기 
def search_union(i, j) :
    
    


# 연합을 이루고 있는 국가들간 국경선 개방하고, 인구수 계산한 결과로 초기화하기
def calc() :





day_cnt = 0
while(True) : 

    for i in range(N) :
        for j in range(N) :
            if(search_union(i, j)) : continue
            else : break # 더이상 인구이동이 없을때
    calc()
    day_cnt += 1
   


print(day_cnt)

 

이제 여기 빈칸에 맞게 차근차근 짜다보면 되겠징

 

 

 

코드

from collections import deque


# 데이터 입력받기
N, L, R = map(int, input().split())
graph = []
for _ in range(N) : 
    graph.append(list(map(int, input().split())))

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


# 연합이 될 수 있는 국가를 BFS로 탐색하여 번호 리스트를 리턴
def search_union(start_x, start_y) :
    union_list = [(start_x, start_y)]
    q = deque([(start_x, start_y)])    
    while(q) :
        x, y = q.popleft()
        visited[x][y] = True
        for i in range(4) : 
            _x, _y = x + dx[i], y + dy[i]
            if _x<0 or _x>= N or _y<0 or _y>=N : # 범위 벗어남
                continue
            if visited[_x][_y] == False :    
                if L <= abs(graph[_x][_y] - graph[x][y]) <= R : 
                    q.append((_x, _y))
                    visited[_x][_y] = True
                    union_list.append((_x, _y))
    return union_list
                      
day_cnt = 0         
while (True) :
    # 하루가 지나면 visited와 연합 리스트 리셋!
    visited = [[False]*N for _ in range(N)]
    done_flag = True
    for i in range(N) :
        for j in range(N) :
            if visited[i][j] == False : 
                area_list = search_union(i, j) # 해당 국가와 연합인 국가의 리스트 얻어옴
                if len(area_list) > 1 : 
                    done_flag = False
                    mean_result = sum([graph[x][y] for x, y in area_list]) // len(area_list)
                    for x, y in area_list :
                        graph[x][y] = mean_result   # 평균 인구로 초기화해준다
    if (done_flag) : break  # 그래프의 모든 칸들 중 연합인 국가들이 하나도 없으면 인구이동이 불가능한 상태
    day_cnt += 1 

print(day_cnt)

 

느낀점 

- flag같은거 안쓰고 논리적 분기로(?) 최대한 깔끔하게 만들고 싶었는데..  그러려는 생각이 더 복잡하게 만든 것 같다

- 그래서 처음에 생각해둔 덩어리대로 만들어 지지 않았다

- 하루가 지나면 리셋된다는거 -> 이거의 기준을 헷갈리지 말자

- 시뮬레이션은 아 ~ 껌이네~ 이러다가 결국 너무 시간이 많이걸린다... 자주 하자 ㄱ-