[이코테] Q21 BFS/DFS_인구 이동(8.21)

링크텍스트

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

예제 입력 1

2 20 50
50 30
20 40

예제 출력 1

예제 입력 2

2 40 50
50 30
20 40

예제 출력 2

0
경계를 공유하는 나라의 인구 차이가 모두 L보다 작아서 인구 이동이 발생하지 않는다.

예제 입력 3

2 20 50
50 30
30 40

예제 출력 3

예제 입력 4

3 5 10
10 15 20
20 30 25
40 22 10

예제 출력 4

2

예제 입력 5

4 10 50
10 100 20 90
80 100 60 70
70 20 30 40
50 20 100 10

예제 출력 5

3

문제풀이

from collections import deque

# 땅의 크기(N), L, R 값을 입력받기
n, l, r = map(int, input().split())

# 전체 나라의 정보(N x N)를 입력 받기
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

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

# 특정 위치에서 출발하여 모든 연합을 체크한 뒤에 데이터 갱신
def process(x, y, index):
    # (x, y)의 위치와 연결된 나라(연합) 정보를 담는 리스트
    united = []
    united.append((x, y))
    # 너비 우선 탐색 (BFS)을 위한 큐 라이브러리 사용
    q = deque()
    q.append((x, y))
    union[x][y] = index # 현재 연합의 번호 할당
    summary = graph[x][y] # 현재 연합의 전체 인구 수
    count = 1 # 현재 연합의 국가 수
    # 큐가 빌 때까지 반복(BFS)
    while q:
        x, y = q.popleft()
        # 현재 위치에서 4가지 방향을 확인하며
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 바로 옆에 있는 나라를 확인하여
            if 0 <= nx < n and 0 <= ny < n and union[nx][ny] == -1:
                # 옆에 있는 나라와 인구 차이가 L명 이상, R명 이하라면
                if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
                    q.append((nx, ny))
                    # 연합에 추가하기
                    union[nx][ny] = index
                    summary += graph[nx][ny]
                    count += 1
                    united.append((nx, ny))
    # 연합 국가끼리 인구를 분배
    for i, j in united:
        graph[i][j] = summary // count

total_count = 0

# 더 이상 인구 이동을 할 수 없을 때까지 반복
while True:
    union = [[-1] * n for _ in range(n)]
    index = 0
    for i in range(n):
        for j in range(n):
            if union[i][j] == -1: # 해당 나라가 아직 처리되지 않았다면
                process(i, j, index)
                index += 1
    # 모든 인구 이동이 끝난 경우
    if index == n * n:
        break
    total_count += 1

# 인구 이동 횟수 출력
print(total_count)

<풀이>-구현,DFS,BFS

이 문제의 해결 아이디어는 다음과 같다.

1. 먼저 국경선을 열지 말지 결정하는 함수를 만든다.

2. 국경선을 전부 열었다면 인구를 문제에 나온 조건에 맞게 이동시킨다.

3. 반복문을 돌면서 더이상 인구이동이 불가능할때까지 위 2번을 반복한다.

생각보다 해결 아이디어는 어렵진 않았지만 위 1번을 구현하는데 있어서 많은 어려움을 겪었다.

필자는 위 1번을 DFS,BFS두가지 방법으로 풀어 그 풀이 모두를 작성하려고 한다.

풀이1-DFS알고리즘 사용

DFS알고리즘을 사용할 경우 가장 중요한건 국경선을 열때 그래프에서 그 해당위치를 저장하는것이다.

만약 해당위치가 국경선을 연다면 그 다음 위치에서 재귀적으로 호출한다.

재귀호출이 다 끝난다면 배열에 저장해놓은 위치에 맞게 인구를 이동시키면 된다.

인구이동이 끝날때마다 '일수'를 저장해놓은 변수에 +1을 해주면 된다.

코드는 다음과 같다.

def dfs(a,b,graph):
    visitied[a][b]=True
    for i in range(4):
        nx = a+dx[i]
        ny = b+dy[i]
        if (0<=nx<n) and (0<=ny<n):
            if (not visitied[nx][ny]) and (l<=(abs(graph[nx][ny] - graph[a][b]))<=r):
                loca.append((nx,ny))
                dfs(nx,ny,graph)
    
    return loca 

<코드>-파이썬
전체 코드는 다음과 같다.

import sys
sys.setrecursionlimit(10000)
n,l,r = map(int,input().split())
popul = []
for _ in range(n):
    popul.append(list(map(int,input().split())))
dx = [-1,0,1,0]
dy = [0,-1,0,1]
#국경선을 열지말지 결정하는 함수
def dfs(a,b,graph):
    visitied[a][b]=True
    for i in range(4):
        nx = a+dx[i]
        ny = b+dy[i]
        if (0<=nx<n) and (0<=ny<n):
            if (not visitied[nx][ny]) and (l<=(abs(graph[nx][ny] - graph[a][b]))<=r):
                loca.append((nx,ny))
                dfs(nx,ny,graph)
    #국경선을 연후 인구이동
    return loca

count = 0
while True:
    visitied = [[False]*n for _ in range(n)]
    flag = False 
    for i in range(n):
        for j in range(n):
            loca = [(i,j)]
            if not visitied[i][j]:
                loca = dfs(i,j,popul)            
            if len(loca)>1:
                flag = True
                sum = 0
                for x,y in loca:
                    sum+=popul[x][y]
                avg = sum//len(loca)
                for a,b in loca:
                    popul[a][b]=int(avg)

    if not flag:
        print(count)
        break
    count+=1   

-while부분 설명-

• while 의 종료조건을 flag=False로 한 이유 :

• 만약 이중 for문을 다 돌았음에도 불구하고 loca배열의 길이가 1이라면 더이상 국경을 열 지역이 없다는 것을 의미한다.

• 만약 loca배열의 길이가 1이상이라면 loca의 원소들은 국경을 연 지역의 위치가 된다.

• 그럼 국경을 연지역의 갯수와 해당 지역의 인구의 총합을 구해 인구를 이동시켜준다.

• 인구를 전부 이동시켰으면 하루가 지난것이므로 count+=1을 해준다.

• 만약 더이상 인구를 이동시킬수 없다면 위에서 설명한대로 flag=True가 되지 못하고 flag = False인채로 유지된다.

• 이때 count를 출력하고 while문을 종료시킨다.

풀이1-BFS알고리즘 사용

우선 탐색을 시작할 위치를 queue에 삽입한다.

그리고 총인구수, 지역의 위치, 현재 연합국가의 갯수를 초기화 하고,그리고 방문여부를 확인한 배열에 큐에 삽입한 위치의 방문여부를 체크해준다.

그리고 연합의 갯수를 저장할 index변수를 초기화 해준다.

queue에 삽입한 원소를 추출한다음 인접지역에 조건을 만족하는 지역이 있다면 해당지역의 위치를 저장하는 배열에 삽입하고 총인구수, 현재 연합국가의 갯수를 갱신한다.

물론 방문여부를 체크하는 배열도 갱신해준다.

위 과정을 queue가 빌때까지 반복한다.

queue가 비었다면 조건을 만족하는 지역의 위치를 담은 배열에서 각 배열의 원소에 해당하는 그래프 위치의 인구수를 문제의 조건대로 갱신한다.

갱신이 완료되면 하루가 지난것이므로 index+=1을 해준다음 index를 리턴한다.

코드는 다음과 같다.

visitied = [[False]*n for _ in range(n)]
from collections import deque
def bfs(a,b,graph):
    queue = deque()
    queue.append((a,b))
    sump=graph[a][b] #총인구수
    country = 1 #연합국가의 갯수
    temp= [(a,b)] #국경을 연지역의 위치 저장하는 배열
    visitied[a][b] = True
    index = 0  #연합의 갯수
    #큐가 빌때까지 열수있는 국경선 열기
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0<=nx<n) and (0<=ny<n):
                if (not visitied[nx][ny]) and (l<=(abs(graph[nx][ny] - graph[x][y]))<=r):
                    queue.append((nx,ny))
                    visitied[nx][ny] = True
                    #국경선을 열수 있다면 연합에 국가를 추가
                    country+=1
                    sump+=graph[nx][ny]
                    temp.append((nx,ny))
    #큐가 비었다면 연합의 갯수 추가하기
    for i,j in temp:
        graph[i][j] = sump//country
    index+=1
    return index

<코드>-파이썬
전체 코드는 다음과 같다.

n,l,r = map(int,input().split())
popul = []
for _ in range(n):
    popul.append(list(map(int,input().split())))
dx = [-1,0,1,0]
dy = [0,-1,0,1]
#국경선을 열지말지 결정하는 함수
visitied = [[False]*n for _ in range(n)]
from collections import deque
def bfs(a,b,graph):
    queue = deque()
    queue.append((a,b))
    sump=graph[a][b]
    country = 1
    temp= [(a,b)]
    visitied[a][b] = True
    index = 0 #연합의 갯수
    #큐가 빌때까지 열수있는 국경선 열기
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0<=nx<n) and (0<=ny<n):
                if (not visitied[nx][ny]) and (l<=(abs(graph[nx][ny] - graph[x][y]))<=r):
                    queue.append((nx,ny))
                    visitied[nx][ny] = True
                    #국경선을 열수 있다면 연합에 국가를 추가
                    country+=1
                    sump+=graph[nx][ny]
                    temp.append((nx,ny))
    #큐가 비었다면 연합의 갯수 추가하기
    for i,j in temp:
        graph[i][j] = sump//country
    index+=1
    return index

ans = 0
while True:
    count = 0
    visitied = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if not visitied[i][j]:
                   count+=bfs(i,j,popul)
    if count == n*n:
        print(ans)
        break
    ans+=1

-while부분 설명-

• 반복문을 돌면서 bfs함수를 실행시킨다음 리턴된 index값(연합의 갯수)를 count에 저장한다.

• 만약 count의 갯수가 그래프의 전체 원소의 갯수와 같다면 더이상 국경을 열 지역이 없다는 것을 의미한다.

• 만약 그렇지 않다면 국경을 몇일동안 열었는지를 저장하는 ans변수에 1을 더해준다.

• 위 설명대로 더이상 국경을 열지역이 없다면 ans를 출력하고 while문을 멈춘다.