BOJ 16234 - 인구 이동

https://www.acmicpc.net/problem/16234www.acmicpc.net

인구 이동이 없을 때까지 인구 이동을 하여서 인구 이동이 몇 번 발생하는지 구하라는 문제입니다.

이 문제는 두 나라의 인구 차이가 L명 이상 R명 이하면 국경선을 열어서 같은 인구수로 합치기 때문에 플러드 필 알고리즘이 필요한 문제입니다.

이 문제는 총 3번의 과정을 통해 풀어보겠습니다.

입력값 받기
플러드 필
출력

1. 입력값 받기

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

일단 이렇게 값을 받고, 인구 이동은 인접한 국가를 확인하고 있으므로 상하좌우로 이동해야 합니다. 그래서 dx, dy 배열도 추가합니다.

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

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

2. 플러드 필

이제 플러드 필을 하면서 인접한 국가에서 인구 차이가 L 이상 R이하이면 국경선을 열어야 합니다. 그러면 이제 국가들이 하나의 연합을 이루고, 이 연합은 여러 개가 있을 수도 있으니 visit 배열을 만들어서 이미 방문한 국가는 방문하지 않도록 합니다.

그리고 인구 이동을 멈출 때까지 계속 진행해야 하므로 while문을 이용해 무한 루프를 만들어줍니다. 그 안에 flag = False라는 변수를 하나 만들어서 인구 이동을 하면 flag = True로 변경해주고, 인구이동을 하지 않으면 flag문을 이용하여 break문으로 빠져나오게 해주면 됩니다.

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

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

그리고 이제 플러드 필을 해주면 됩니다. 플러드 필은 큐(BFS), 스택이나 재귀(DFS)를 이용하면 되는데, 저는 큐를 이용해서 만들겠습니다.

그러면 collections.deque를 불러오고, 2중 for문을 돌려서 visit[x][y] = 0인 곳을 찾아 플러드필을 하면 됩니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque()
                q.append((i,j))
                visit[i][j] = 1
                blah blah

기본적인 플러드 필에 필요한 변수들은 위와 같고, 이제 인구 이동 문제에 필요한 변수는 국경선을 열어서 인구를 전부 합쳐야 하므로 연합의 위치, 연합의 인구수를 구하는 변수를 추가해야 합니다.

이것은 union = [] 과 population = 0이라는 변수로 설정하겠습니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque(); q.append((i,j))
                visit[i][j] = 1
                union = [(i,j)]
                population = arr[i][j]
                blah blah

이제 플러드 필을 시작하면 됩니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque(); q.append((i,j))
                visit[i][j] = 1
                union = [(i,j)]
                population = arr[i][j]
                while q:
                    x, y = q.popleft()
                    blah blah

여기서 주의할 점은 arr[nx][ny]은 배열 밖으로 나가지 말아야 하고, visit[nx][ny] = 0, abs(arr[x][y] - arr[nx][ny])가 L이상 R이하여야만 연합을 이룰 수 있다는 점입니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque(); q.append((i,j))
                visit[i][j] = 1
                union = [(i,j)]
                population = arr[i][j]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0 and L <= abs(arr[x][y] - arr[nx][ny]) <= R:
                            q.append((nx,ny))
                            visit[nx][ny] = 1
                            union.append((nx,ny))
                            population += arr[nx][ny]

이제 플러드 필을 마쳤으면 연합을 이루는 국가들이 다 모였거나, 조건을 맞추지 못하여 국경선을 열지 못한 나라도 있을 겁니다.

그래서 len(union) > 1 일 때만 인구 이동을 해주면 됩니다. 이때 flag = True로 설정해주는 것도 잊지 말고 해야 합니다. 인구 이동은 문제에 나온 것처럼 population // len(union) 값을 arr[x][y]에 넣어주면 됩니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque(); q.append((i,j))
                visit[i][j] = 1
                union = [(i,j)]
                population = arr[i][j]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0 and L <= abs(arr[x][y] - arr[nx][ny]) <= R:
                            q.append((nx,ny))
                            visit[nx][ny] = 1
                            union.append((nx,ny))
                            population += arr[nx][ny]
                if len(union) > 1:
                    flag = True
                    for x, y in union:
                        arr[x][y] = population // len(union)

3. 출력

이제 마지막으로 출력을 해주면 됩니다. 인구 이동이 몇 번 발생하는지 출력해야 하므로 t = 0이라는 변수를 만들어서 추가해주고, 인구 이동을 못 하면(flag = False) break문을 걸어서 while문을 빠져나오고, 아니라면 t += 1을 해주면 됩니다.

코드가 길어서 코드를 추가한 곳에 주석을 달아두었습니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, L, R = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
t = 0 # 추가

while 1:
    visit = [[0]*n for _ in range(n)]
    flag = False

    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                q = deque(); q.append((i,j))
                visit[i][j] = 1
                union = [(i,j)]
                population = arr[i][j]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0 and L <= abs(arr[x][y] - arr[nx][ny]) <= R:
                            q.append((nx,ny))
                            visit[nx][ny] = 1
                            union.append((nx,ny))
                            population += arr[nx][ny]
                if len(union) > 1:
                    flag = True
                    for x, y in union:
                        arr[x][y] = population // len(union)
    # 추가
    if flag: t += 1
    else: break

print(t)

PreviousBOJ 8972 - 미친 아두이노 NextBOJ 17135 - 캐슬 디펜스

Last updated 4 years ago

Was this helpful?