[Baekjoon]16234. 인구이동 (Gold_4) 2024/4/15

문제 제목	정답률	난이도
인구이동	39%	Gold_4

 

문제요약

정사각형 땅의 크기 N, 최소 인구차이 L, 최대 인구차이 R이 첫 번째 줄에 주어진다.

1~N+1줄에는 나라별 인구수가 주어진다.

국경선을 공유하는 두 나라의 인구 차이가 L이상 R이하이면 두 나라가 공유하는 국경선을 하루동안 연다.

국경선이 열려있고, 인접한 칸을 이용해 이동할 수 있다면 해당 나라들을 연합이라고 한다.

연합하는 나라의 인구수는 sum(연합 인구수)/(연합하는 나라 수)이다.

인구 이동이 발생하지 못할때까지 인구 이동을 지속한다.
조건 1) 1 <=N <=50, 1 <=L <=R <=100, 0 <=인구수 <=100 

 

인구이동을 진행하는 날짜를 반환하여라 

 

풀이

Step1. 연합은 상, 하, 좌, 우로 이루어짐으로 bfs이용

• bfs(graph, visited, now_idx)

Step2. 종료조건 생각 : break_flag 이용

• 모든 row, col에 대해 bfs가 일어나지 않으면 종료한 뒤, 해당 날짜 반환

 

코드

N, L, R = list(map(int, input().split()))
population_list = [[] for _ in range(N)]
for row_idx in range(N):
    population_list[row_idx] = list(map(int, input().split()))
  
def bfs(graph, visited, now_row, now_col, L, R):
    bfs_stack = [[now_row, now_col]]
    answer = [[now_row, now_col]]

    while len(bfs_stack) > 0:
        x, y = bfs_stack.pop()
        now_value = graph[x][y]
        # 상
        if x > 0:
            if visited[x-1][y] == 0 and abs(now_value-graph[x-1][y]) >= L and abs(now_value-graph[x-1][y]) <= R:
                visited[x-1][y] = 1
                bfs_stack.append([x-1, y])
                answer.append([x-1, y])
        # 하
        if x < len(graph)-1:
            if visited[x+1][y] == 0 and abs(now_value-graph[x+1][y]) >= L and abs(now_value-graph[x+1][y]) <= R:
                visited[x+1][y] = 1
                bfs_stack.append([x+1, y])
                answer.append([x+1, y])
        # 좌
        if y > 0:
            if visited[x][y-1] == 0 and abs(now_value-graph[x][y-1]) >= L and abs(now_value-graph[x][y-1]) <= R:
                visited[x][y-1] = 1
                bfs_stack.append([x, y-1])
                answer.append([x, y-1])
        # 우
        if y < len(graph)-1:
            if visited[x][y+1] == 0 and abs(now_value-graph[x][y+1]) >= L and abs(now_value-graph[x][y+1]) <= R:
                visited[x][y+1] = 1
                bfs_stack.append([x, y+1])
                answer.append([x, y+1])

    if len(answer) > 1:
        move_value = sum([population_list[row][col]
                         for row, col in answer])//len(answer)
        for row, col in answer:
            population_list[row][col] = move_value
        return False

    return True


day = 0
while day <= 2000:
    break_flag = True
    visited = [[0 for _ in range(N)] for _ in range(N)]
    for row_idx in range(N):
        for col_idx in range(N):
            if visited[row_idx][col_idx] == 0:
                visited[row_idx][col_idx] = 1
                break_flag = break_flag & bfs(
                    population_list, visited, row_idx, col_idx, L, R)
    if break_flag == False:
        day += 1
    else:
        break
print(day)