Python으로 푸는 백준 16234. 인구이동

백준 16234. 인구이동

인구 이동이 시작되는 날,

두 나라의 인구 차이가 L명 이상, R명 이하라면, 

두 나라가 공유하는 국경선을 개방하여 인구 이동을 시킨다.

이러한 인구이동이 몇 번 발생하는 지 구하는 프로그램을 작성하시오

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기

문제를 틀렸다면 생각 해 볼 조건들

1. 친구의 친구라면 걔도 내 친구다.

: A, B, C, D 국가가 있을 때, A, C, D가 연합이다. A, B 사이에는 국경을 개방해야 하는 조건이 충족되지 않았지만 연합 국가(C, D) 중 한 국가라도 B와 연합이 가능하다면 A, B는 연합국가가 된다. (나(A)와 B가 직접적으로 아는 사이가 아니더라도, 내(A) 친구가 B와 친구라면 B도 내 친구라는 개념, 친구의 친구면 걔도 내 친구ㅎㅎ) 한번 방문했다고 A와 B가 연합이 가능한지 보았다고 visited 체크해주면 다른 연합국가와의 연합 가능 여부를 체크 못할 수도 있다. 

2. 인구 이동 수를 세는 기준은 몇 개의 연합이 생기는지 여부가 아니다.

: 모든 국가의 연합 가능 여부를 탐색하였을 때, 그 날 하루 연합이 단 하나라도 발생했는 지에 대한 발생 여부이다. 

3. 인구 이동은 연합 가능한 모든 국가를 체크하고, 인구 이동을 시켜주어야 시간 초과가 안난다. (그래도 파이썬은 시간초과가 나던데..)

문제 풀이

나는 시간 초과가 나서 python3로는 문제를 푸는데 성공하진 못했다. 그래도 pypy3로는 통과했으니 로직 자체에는 에러가 없으므로 일단 코드를 정리해서 올리도록 하겠다.

python3로 문제를 푼 사람은 여태 한명밖에 없던데, 어떻게 풀었는지 너무 궁금하다.

이 문제를 풀 때 주의할 점은 <문제를 틀렸다면 볼 사항>이라고 해서 위에 따로 정리해두었다. 

코드 리뷰

이 문제는 다시 한번 보고, 나중에 내공이 쌓였을 때 다시 한번 풀어봐야할 문제이다. 

열심히 풀었는데 파이썬으로 통과 못하면 너무 속상하다...근데 누군가는 풀었으니 내 내공이 부족한 거겠지..

파이썬 코드

import sys
input = sys.stdin.readline
 
dx = [0,0,-1,1]
dy = [-1,1,0,0]
 
def nextStart(n, visited):
    for i in range(n):
        for j in range(n):
            if visited[i][j] == -1:
                return (i, j)
    return False
 
 
def checkrange(frist_v, second_v,  l, r):
    value = abs(frist_v - second_v)
    if l <= value <= r:
        return True
    return False
 
# 연합 국가를 찾는다
def union(n, l, r, visited, ground):
    country = n*n
    startPoint = [(0, 0)]
    union_num= 0
    union_count = 0
    flag = True
    arr = []
    immigration_count = 0
    next_pos = None
 
 
    while flag:
        # 현재 연합의 총 인구수, 총 연합 국가 수
        total = 0
        count = 0
        # 연합을 찾는다
        while startPoint:
            pos = startPoint.pop()
            x, y = pos
            visited[x][y] = union_num
            frist_value = ground[x][y]
            total += frist_value
            count += 1
            country -= 1 # 체크하지 않고 남은 국가 수
 
            for i in range(4):
                temp_x = pos[0] + dx[i]
                temp_y = pos[1] + dy[i]
                # 범위 초과 및 이미 방문한 곳 체크
                if temp_x < 0 or temp_y < 0 or n <= temp_x or n <= temp_y or visited[temp_x][temp_y] != -1:
                    continue
                second_value = ground[temp_x][temp_y]
                # 조건 체크
                if checkrange(frist_value, second_value, l, r):
                    # 방문 (예정) 표시
                    visited[temp_x][temp_y] = union_num
                    startPoint.append((temp_x, temp_y))
                else:
                    # 이 지점이 다음 스타트할 지점 (nextStart를 최대한 피하기 위한 가지 치기)
                    if i == 3 and len(startPoint) == 0:
                        next_pos = (temp_x, temp_y)
 
        # union_num를 index로 하는 arr 원소 자리에 갱신할 인구수를 저장
        new_value = total // count
        arr.append(new_value)
        union_num+= 1
        union_count += 1
 
        if country == 0:
            # 단 하나의 연합도 이뤄지지 못한 경우
            if union_count == n*n:
                flag = False
                break
            #  모든 국가가 연합인 경우
            if union_count == 1:
                flag = False
                immigration_count += 1
                break
 
            # 새로운 인구수로 갱신
            for i1 in range(n):
                for j1 in range(n):
                    # 인구수를 가져옴
                    index = visited[i1][j1]
                    visited[i1][j1] = -1
                    ground[i1][j1] = arr[index]
 
            # 새로운 탐색을 위해 초기화
            country = n * n
            startPoint = [(0, 0)]
            union_num = 0 # 연합 번호
            union_count = 0
            immigration_count += 1
            arr = []
        else:
            if next_pos:
                startPoint.append(next_pos)
                # 다시 초기화
                next_pos = None
            else:
                # 다음 탐색 지점 추가
                startPoint.append(nextStart(n, visited))
 
    return immigration_count
 
def solve(n, l, r, ground):
    visited = [[-1]*n for i in range(n)]
    return union(n, l, r, visited, ground)
 
 
if __name__ == "__main__":
    n, l, r = map(int, input().strip().split())
    ground = []
    for i in range(n):
        land = list(map(int, input().strip().split()))
        ground.append(land)
    print(solve(n, l, r, ground))

#16234 인구이동 #16234 인구이동 Python #16234 인구이동 파이썬 #파이썬 16234