[백준/Swift] 16234 : 인구이동

• BFS로 인구이동 문제 풀기

• 16234 : 인구이동 / 문제 소개
• 풀이 과정
• 코드 구현

 

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

16234번: 인구 이동

 

16234 : 인구이동 / 문제 소개

 

N*N크기에서 각 1*1 칸의 땅은 '나라'가 존재한다.

이 칸마다 고유한 인구수가 존재한다.

 

국경선이 열리면 그 인접한 나라들 끼리는 연합을 이룬다

이때 인구이동이 시작된다. 그리고 연합에 포함되는 국가의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수) 인구수 만큼 된다.

 

두 나라의 인구수 차이가 L이상 R이하인 나라가 더이상 존재하지 않아 연합을 이룰 수 없을 때 비로소 인구 이동은 막을 내린다.

 

   문제에서 주어진 키워드

• 나라에는 A[r][c]( = x명)이 살고 있음
• 나라 간 국경선 존재
• (인구이동)조건에 의해 국경선 열릴 수 있음
• 연합 ( 두 나라간 차이가 L보다 크거나 같고 R보다 작거나 같을 때!!)
• 인구 이동은 며칠 동안 발생하는가?

 

 

풀이 과정

 

맨 처음에 이 문제가 어떻게 bfs로 풀어나갈 수 있는지 고민을 했습니다.

여기서  (1,0) = 15 와 (1,1) = 30 두 나라간 국경선은 존재하지만 타 나라에 의해 연결 되었기 때문에 한개의 연합으로 간주됩니다.

따라서 위 조건에 의해 ( 10 + 15 + 20 + 20 + 30 + 25 + 22 ) / 7 = 20. 연합 국가에 속한 국가들은 모두 인구수가 20이 됩니다.

이때 초기 상태에서 Day1을  진행 할 수 있도록 최소 두 나라 이상이 연합을 맺을 수 있는 나라를 찾는 방법이 필요합니다.

 

첫째 날이 지난 후에

또 나라간 연합이 존재하므로 Day2 가 되면서 인구이동이 됩니다.

(20 + 20 + 10) / 3 = 16

더이상 L <= 두 나라간 차이 <= R 인 나라가 존재 하지 않기 때문에 인구 이동은 일어나지 않습니다.

고로 답은 2가 됩니다.

---

어떻게 이 문제의 국경선을 체크 할 것인가? 한 나라는 최소 2개~ 4개의 국경선을 가질 것인데.. 고민을 했었습니다.

하지만 생각보다 간편하게 해결할 수 있었습니다. 단순히 국경선이 1개라도 오픈 되어있는 나라라면 타 나라와 인접하고 결국 연합 국가가 된다는 것은 bfs탐색을 통해 어느 특정 나라만 지목했을 때 (인구이동 조건에 맞는 L <= 나라간 인구 차이 <= R )연합 국가가 존재하면 한 번의 bfs탐색을 통해 가능하다는 것입니다. +_+

---

이 문제를 풀어나가기 위해서는 '연합'가능성이 있는 나라를 파악하는 것입니다. 

Day0 에서 Day1로 가기 위해서는 반드시 연합 국가가 존재해야 합니다.

연합 국가는 최소 1개~x개가 될 수 있습니다.

 

연합 가능성이 있는 나라 파악을 할 때 저는 단순하게 맵의 완전 탐색을 해나가면서 만약 특정 위치에서 이웃간 인구수 차이가 L R(인구이동) 조건에 맞다면 bfs탐색을 하고 bfs 탐색을 하면서 queue에 저장시킨 좌표들을 따로 리스트에 저장해 두는 방식으로 구현을 했습니다.

또한 bfs탐색을 한 좌표는 다시 탐색 못하게 방문체크를 했습니다.

//실제 코드와 달리 많이 생략됨

여기서 queueList는 한번의 bfs 탐색을 한 후에 queue에 남아있는 연합 국가의 정보가 들어있는데 이걸 queueList에 저장했다.

Day0에서 Day1로 가게 된다면 queueList에는 특정 연합 국가들의 좌표들이 존재할 것이다!!!

	for y in 0..<land.n
        {
            for x in 0..<land.n
            {
                if !visited[y][x]
                {
                    for (dx,dy) in direction
                    {
                        let (nx,ny) = (x + dx, y + dy)
                        if nx < 0 || nx > land.n - 1 || ny < 0 || ny > land.n - 1
                        {
                            continue
                        }
                        let rc = abs(land.map[ny][nx] - land.map[y][x])
                        if rc >= land.minMove && rc <= land.maxMove
                        {
                            bfs(land, &visited, &queue)
                            break
                        }
                    }
                    queueList.append(queue)
                }
            }
        }

이때 큐 또한 사용하기 쉽게 클래스로 만들었는데..

typealias Element = (Int,Int)
/**
 * totalSum은 연합 국가가 된 모든나라의 합을 저장한다+_+
 */
class Q
{
    var queue    : [Element]
    var index    : Int
    var totalSum : Int
    init()
    {
        queue    = [Element]()
        index    = 0
        totalSum = 0
    }
}

여기서 queue라는 배열의 removeFirst() 함수를 사용하지 않고 index를 훑어 나갔다..

while queue.count != queue.index { ... }

다음에 큐의 위치를 탐색할 때 index 만 0으로 초기화 해주면 연합 나라들을 다시 탐색할 수있는데 이미 totalSum으로 연합국가를 찾는 즉시 더해갔기 때문에 이 과정은 필요가 없어졌다..

 

위 과정을 반복하면 결국에는

L R 조건에 부합하는 연합 나라가 존재하지 않고 그 결과.. Day가 답이 되는 것이다.

 

코드 구현

 

아직 제 실력이 많이 부족해 코드가 깁니다 ㅠㅠ 

import Foundation

//x,y 좌표
typealias Element = (Int,Int)

//탐색 방향
let direction     = [(-1,0),(1,0),(0,1),(0,-1)]

/**
 * @param queue     : '연합'에 속한 나라들의 좌표가 저장됨
 * @param index     : queue를 탐색하기 위한 index (재사용 good)
 * @param totalSum  : 연합에 속한 나라들을 탐색해 갈때 즉시 totalSum으로 연합 에 포함되는 인구수 다 더함.
 *                  추후 queue.count를 통해 연합 국가 개수 파악 가능!!
 */
class Q
{
    var queue    : [Element]
    var index    : Int
    var totalSum : Int
    init()
    {
        queue    = [Element]()
        index    = 0
        totalSum = 0
    }
}

/**
 * N x N 땅의 정보가 들어있습니다.
 *
 * @param n               : 나라 크기
 * @param minMove  : L조건 최소 이동 가능한 인구수
 * @param maxMove : R조건 최대 이동 가능한 인구수
 * @param map          : 나라들 인구수 있음
 */
class mapInfo
{
    let n       : Int
    let minMove : Int
    let maxMove : Int
    var map     : [[Int]]
    init()
    {
        let input = readLine()!.split(separator: " ").map{Int(String($0))!}
        n       = input[0]
        minMove = input[1]
        maxMove = input[2]
        map     = Array(repeating: [Int](), count: n)
        for i in 0..<n
        {
            map[i] = readLine()!.split(separator: " ").map{Int(String($0))!}
        }
    }
}

/**
 * 아래 메인 문장에서 연합국가의 조건이 된다면 bfs탐색을 통해 q에 연합 국가 좌표들 모두 저장
 * visited 를 통해 q에 중복되는 나라 좌표는 있을 수가 없음
 * 또한 q의 totalSum에 방문되는 연합 국가 인구수를 모조리 더함!!
 */
func bfs(_ land : mapInfo, _ visited : inout [[Bool]], _ q : inout Q)
{
    let (x,y) = q.queue[q.index]
    q.totalSum += land.map[y][x]
    
    while(q.queue.count != q.index)
    {
        let (curX,curY) = q.queue[q.index]
        q.index += 1
        for (dx,dy) in direction
        {
            let (nx,ny) = (curX + dx, curY + dy)
            if nx < 0 || nx > land.n - 1 || ny < 0 || ny > land.n - 1
            {
                continue
            }
            if !visited[ny][nx]
            {
                let rc = abs(land.map[ny][nx] - land.map[curY][curX])
                if rc >= land.minMove && rc <= land.maxMove
                {
                    q.totalSum += land.map[ny][nx]
                    
                    visited[ny][nx] = true
                    q.queue.append((nx,ny))
                }
            }
        }
    }
}
/**
 * @param land         : 국가 인구수들 저장됨
 * @param day          : 날
 * @param canMove : 국가들 간 연합 조건에 부합되는 국가가 있는가? 있다면 true
 */
func BOJ_16234()
{
    var land = mapInfo()
    var day  = 0
    var canMove = true
    /**
     * while문 시작하자마자 canMove를 false 함으로 나라들 모두 탐색했을 때 canMove = true가 되지 않으면
     * 인구이동 할 연합국가가 없는것으로 간주. 종료됨.
     *
     * 매번 queueList를 초기화 해주는데 이때마다 새로 연합국가가되는 나라들의 좌표들을 갖는 n개의 연합 들이 저장됨
     */
    while canMove
    {
        var visited   = Array(repeating: Array(repeating: false, count: land.n), count: land.n)
        var queueList = [Q]()
        canMove       = false
        for y in 0..<land.n
        {
            for x in 0..<land.n
            {
                if !visited[y][x]
                {
                    var queue = Q()
                    //이 flag는 연합국가가 있다면? true로 하고 나중에 queueList에 bfs로 연합국가를 탐색한 후에 queue를 집어 넣기 위한 변수
                    var flag  = false
                    for (dx,dy) in direction
                    {
                        let (nx,ny) = (x + dx, y + dy)
                        if nx < 0 || nx > land.n - 1 || ny < 0 || ny > land.n - 1
                        {
                            continue
                        }
                        let rc = abs(land.map[ny][nx] - land.map[y][x])
                        if rc >= land.minMove && rc <= land.maxMove
                        {
                            flag      = true
                            canMove   = true
                            visited[y][x] = true
                            queue.queue.append((x,y))
                            bfs(land, &visited, &queue)
                            break
                        }
                    }
                    if flag == true
                    {
                        queueList.append(queue)
                    }
                }
            }
        }
        /**
         * 만약 canMove가 true면 연합국가가 존재하는 것이므로
         * 연합국가의 평균값을 land.map에 새로 할당!!
         */
        if canMove
        {
            day += 1
            for i in 0..<queueList.count
            {
                queueList[i].totalSum = queueList[i].totalSum/queueList[i].queue.count
                queueList[i].index = 0
                while queueList[i].queue.count != queueList[i].index
                {
                    let (curX,curY) = queueList[i].queue[queueList[i].index]
                    queueList[i].index += 1
                    land.map[curY][curX] = queueList[i].totalSum
                }
            }
        }
    }
    print(day)
}
BOJ_16234()