[백준 16234번 - 인구이동]-파이썬

solved.ac 난이도 : GOLD5

백준   16234번- 파이썬 풀이

 

<문제>

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

16234번: 인구 이동

<풀이>-구현,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문을 종료시킨다.

 

728x90

풀이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문을 멈춘다.

 

-마치며-

정말 고생했던 문제다.

필자는 처음 시도 할때 DFS풀이법으로 시도했다. 하지만 재귀호출하는 부분에서 다음과 같이 작성했더니 인구이동이 제대로 안이루어져 많은 고생을 했다.

sump = 0 #연합국가의 총 인구수
country= 0 #연합국가의 수
#국경선을 열지말지 결정하는 함수
loca = []
def dfs(a,b,graph):
    global sump
    global country
    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):
                sump+=graph[nx][ny]
                visitied[nx][ny] = True
                country+=1
                loca.append((nx,ny))
                dfs(nx,ny,graph)
                
    #국경선을 연후 인구이동
    for i,j in loca:
        graph[i][j] = sump//country

 

재귀부분이 정확하지 않아 인구이동에서 계속해서 잘못된 결과가 나왔다.

이 경험을 계기로 재귀함수부분을 더 열심히 해야겠다고 느꼈다.

 

참고로 이문제는 삼성전자  sw역량테스트 기출문제고 '이코테with파이썬'에도 나와있다. 책에 나온 풀이는 다음과 같다.

from collections import deque
n,l,r = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
dx = [-1,0,1,0]
dy = [0,-1,0,1]
#국경선을 열지말지 결정하는 함수

def bfs(x,y,index):
    queue = deque()
    queue.append((x,y))
    summary=graph[x][y]
    count = 1
    unitied = []
    unitied.append((x,y))
    union[x][y] = index
   
    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) and (union[nx][ny]==-1) :
                if l<=(abs(graph[nx][ny] - graph[x][y]))<=r:
                    queue.append((nx,ny))
                    union[nx][ny] = index
                    #국경선을 열수 있다면 연합에 국가를 추가
                    count+=1
                    summary+=graph[nx][ny]
                    unitied.append((nx,ny))
 
    for i,j in unitied:
        graph[i][j] = summary//count
    return 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:
                bfs(i,j,index)
                index+=1
    if index == n*n:
        break
    total_count+=1
print(total_count)

이 풀이에서는 union배열을 설정해 연합을 이루고 있는 위치끼리는 같은 index값을 취하고 있게끔 하고 있다. 또한 해당지역에서 인구이동이 끝난다음에는 index값을 +1증가시켜 다른 연합끼리는 다른 번호를 갖고 있다.

만약 index값이 n*n이라면 모든 국경선이 닫혀있는것을 의미하므로 while문이 멈춘다.