21_인구 이동

16234번: 인구 이동

 

풀긴 풀었는데, 시간 복잡도가 최악임

BFS를 활용해서, 인구 이동할 수 있는 국가들을 담은 리스트를 반환해주는 함수를 만들어주고,

해당 리스트에 담긴 원소(인구)의 합을 원소의 길이를 나눈 값으로 해당 국가들의 값(인구)으로 바꿔준다.

 

그리고, 만약, 위 과정을 겪었을 때, 그래프의 원소가 변하지 않았다면, 더 이상 인구이동을 하지 않은 것이므로 반복문을 종료한다.

 

---

내 풀이 코드

# 16234번: 인구 이동
from collections import deque
import copy

n, l, r = map(int, input().split())
graph = []
for _ in range(n):
    row = list(map(int, input().split()))
    graph.append(row)

visited = [[False] * n for _ in range(n)]

# graph[i][j]에서 인구 이동할 수 있는 국가들을 BFS로 탐색
def bfs(i, j):
    queue = deque([(i, j)])
    country = [(i, j, graph[i][j])] # graph[i][j]에서 인구 이동할 수 있는 국가를 담은 리스트
    visited[i][j] = True

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

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx >= 0 and nx < n and ny >= 0 and ny < n:
                temp = abs(graph[x][y] - graph[nx][ny])
                if not visited[nx][ny] and temp >= l and temp <= r:
                    queue.append((nx, ny))
                    country.append((nx, ny, graph[nx][ny]))
                    visited[nx][ny] = True

    return country


index = 0
while True:
    temp_graph = copy.deepcopy(graph) # 만약 temp_graph와 grap
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                temp_total = 0
                country = bfs(i, j)
                if len(country) == 0:
                    continue

                for c in country:
                    temp_total += c[2]
                population = temp_total // len(country)
                for c in country:
                    graph[c[0]][c[1]] = population


    # 만약 temp_graph와 graph의 원소가 모두 동일하다면, 더 이상 인구 이동이 안 일어난 것
    answer = True
    for i in range(n):
        for j in range(n):
            if temp_graph[i][j] != graph[i][j]:
                answer = False

    # 인구 이동이 안 일어난 경우, 정답을 출력하고 반복문 종료
    if answer:
        print(index)
        break

    # 방문 여부 초기화
    visited = [[False] * n for _ in range(n)]
    # 하루 경과
    index += 1

 

위 방식으로 풀 경우 시간복잡도가 최악이다.

 

그래서 풀긴했으나, 더 효과적인 풀이가 있을 것 같아서 풀이 코드를 봤다.

 

---

풀이 코드

근데 책 풀이 제출하면 시간초과가 뜨더라.

 

그래서 내 풀이에서 조금 개선해서 시간을 줄였다.

 

개선한 내 풀이 코드

# 16234번: 인구 이동
from collections import deque
import copy

n, l, r = map(int, input().split())
graph = []
for _ in range(n):
    row = list(map(int, input().split()))
    graph.append(row)

visited = [[False] * n for _ in range(n)]

# graph[i][j]에서 인구 이동할 수 있는 국가들을 BFS로 탐색
def bfs(i, j):
    queue = deque([(i, j)])
    country = [(i, j, graph[i][j])] # graph[i][j]에서 인구 이동할 수 있는 국가를 담은 리스트
    visited[i][j] = True

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

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx >= 0 and nx < n and ny >= 0 and ny < n:
                temp = abs(graph[x][y] - graph[nx][ny])
                if not visited[nx][ny] and temp >= l and temp <= r:
                    queue.append((nx, ny))
                    country.append((nx, ny, graph[nx][ny]))
                    visited[nx][ny] = True

    return country


index = 0 # 인구이동을 한 날짜 수

while True:
    answer = True # 인구 이동이 일어났다면 True
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                temp_total = 0
                country = bfs(i, j)

                # country 리스트의 길이가 1보다 크다면 인구이동이 일어날 것.
                if len(country) > 1:
                    answer = False

                # 인구 이동 과정
                for c in country:
                    temp_total += c[2]
                population = temp_total // len(country)
                for c in country:
                    graph[c[0]][c[1]] = population


    # 인구 이동이 안 일어난 경우, 정답을 출력하고 반복문 종료
    if answer:
        print(index)
        break

    # 방문 여부 초기화
    visited = [[False] * n for _ in range(n)]
    # 하루 경과
    index += 1

 

빡세다 ㅎㅎ