백준 16234번 인구 이동 - SWIFT

문제

---

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번 보다 작거나 같은 입력만 주어진다.

 

 

출력

---

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

 

 

문제 링크

---

16234번: 인구 이동

 

 

풀이

---

이 문제에서 주목해야할 점은 연합이다.

연합은 한 개만 생기는 것이 아니라 같은 날 여러 개가 생길 수 있다.

따라서 연합을 넣는 2차원 튜플(y, x) 배열과 연합을 구하는 BFS함수를 만들었다.

또 BFS함수를 위한 visit 배열과 BFS큐도 만들어줬다.▼

 

 

프로그램 동작

---

1. 값이 false인 visit이 나올 때 까지 visit을 순회한다.▼

 

 

2. false인 visit이 나왔다면, 해당 visit은 true로 바꿔주고, 연합 목록에 넣어준다.

그 다음 상, 하, 좌, 우 4방향을 검사해본다.▼

 

 

만약 false인 visit이 없다면 함수를 종료한다.

 

3. 4방향에 있는 값과 현재 값의 차가 조건에 맞는다면 BFS큐에 좌표를 넣어준다.

BFS큐에 들어간 좌표들은 visit에서 그 좌표를 true로 바꿔준다.

BFS함수는 BFS큐가 다 소진될 때 까지 반복된다.

4방향에 있는 값이 조건에 맞지 않아서 BFS큐에 들어가지 못한다면, BFS큐의 값이 부족해서 종료된다.

BFS가 종료되면 다시 순회로 돌아간다.▼

 

 

4. 발견한 false는 true로 바꾸고, 다시 4방향을 확인한다.

이 때 방문한 곳은 확인하지 않는다.▼

 

 

5. 조건에 맞는 곳이 나오면 이를 BFS큐에 집어넣고 현재 값을 BFS큐의 다음 값으로 바꿔준다.▼

 

 

6. 앞의 과정인 4방향 탐색을 다시 해준다.▼

 

 

7. 반복▼

 

 

8. BFS큐의 끝에 도달했는데 추가된 게 없으므로 한 연합은 여기까지인 것이다.▼

 

 

9. 노란색으로 칠해진 부분들이 한 연합인 것인데, 이 연합 정보는 전부 BFS큐에 들어가 있다.▼

 

 

따라서 BFS큐에 있는 정보를 연합 배열에 넣어주면 된다.▼

 

 

10. 이 과정을 visit이 전부 true가 될 때 까지 반복해준다.visit이 전부 true가 됐을 때의 연합정보는 이렇다.

(한 개 짜리도 연합 배열에 있지만 프로그램에서는 한 개짜리는 연합취급을 안한다.) ▼

 

 

11. 연합을 전부 구했으면 이들 값을 변경해준다.문제에서는 연합의 원소의 평균값으로 연합의 원소들을 바꿔주라고 했다.▼

 

 

12. 값을 변경했으면 앞의 과정을 전부 반복해준다. 앞의 과정 한 번당 1일이다.

 

13. 더 이상 연합이 생기지 않게 된다면, 연합 배열에는 각각의 나라로 연합이 채워져 있을 것이고, 이 개수는 N^2이다.즉, 연합 배열의 행 개수가 N^2이 되면 종료하고 답을 출력한다.

 

Swift 코드

---

let NLR = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = NLR[0], L = NLR[1], R = NLR[2]
var map = Array(repeating: [Int](), count: N)
var visit = Array(repeating: Array(repeating: false, count: N), count: N)
let dy = [0, 0, 1, -1]
let dx = [1, -1, 0, 0]
var BFSq = [(Int, Int)]()
var union = [[(Int, Int)]]()
var answer = 0
for i in 0..<N {
    map[i] = readLine()!.split(separator: " ").map { Int(String($0))! }
}

func BFS(_ startY: Int, _ startX: Int) {
    var BFSq = [(Int, Int)]()
    var index = 0
    BFSq.append((startY, startX))
    visit[startY][startX] = true

    while index < BFSq.count {
        let cur = BFSq[index]
        index += 1
        for i in 0..<4 {
            if cur.0 + dy[i] < 0 || cur.0 + dy[i] >= N || cur.1 + dx[i] < 0 || cur.1 + dx[i] >= N {
                continue
            }
            if visit[cur.0 + dy[i]][cur.1 + dx[i]] == true {
                continue
            }
            let tmp = abs(map[cur.0][cur.1] - map[cur.0 + dy[i]][cur.1 + dx[i]])
            if tmp >= L, tmp <= R {
                visit[cur.0 + dy[i]][cur.1 + dx[i]] = true
                BFSq.append((cur.0 + dy[i], cur.1 + dx[i]))
            }
        }
    }
    union.append(BFSq)
}
while true {
    union = [[(Int, Int)]]()
    visit = Array(repeating: Array(repeating: false, count: N), count: N)
    for i in 0..<N {
        for j in 0..<N {
            if visit[i][j] == false {
                BFS(i, j)
            }
        }
    }
    if union.count == N * N {
        break
    }
    for i in 0..<union.count {
        var sum = 0
        if union[i].count == 1 {
            continue
        }
        for j in union[i] {
            sum += map[j.0][j.1]
        }
        for j in union[i] {
            map[j.0][j.1] = sum / union[i].count
        }
    }
    answer += 1
}

print(answer)

 

 

이런 순서로 문제를 해결했는데, Swift에서 주의할 점이 하나 있다.

코드를 보면 BFSq라고 큐로 사용하려고 만든 배열이 하나 있는데, BFSq에서 실제 pop처럼 원소를 제거하면 안된다.

여기서 말하는 제거는 `remove()`함수를 사용하는 것이다.

 

이유는 두 가지인데,

첫번째 이유는 BFSq에 있는 내용을 전부 union배열로 옮겨야하기 때문이다.

만약 BFSq에서 실제로 remove를 해버린다면 연합정보를 visit배열 순회로 다시 구해야한다.

상당히 귀찮아지고, 시간도 많이 걸리므로 이렇게 하면 안좋다.

 

두번째 이유는 remove()의 시간복잡도 때문이다.

보통 큐라고 하면 선입선출로 가장 먼저 들어온 것부터 큐에서 빼버린다.

그러면 BFSq에서 removeFirst()나, remove(at: 0), 또는 reverse() 한 후 popLast()를 사용할 것이다.

문제는 removeFirst(), remove(at:0), reverse()의 시간복잡도는 O(N)이다.

 

reverse()야 그렇다 치는데, removeFirst()와 remove(at:0)은 인덱스 검색을 하는 것도 아닌데 왜 O(N)일까?

인덱스를 제거하고 나면 그 인덱스 빈자리에 나머지 원소들을 끌어와야 하기 때문이다.

그래서 BFSq에 많은 원소가 들어가게 되면 지우는데 시간이 많이 소모되어 제한시간을 넘기게 된다.

추천하는 방법은 index 변수를 만들어서 실제로 제거하는 것이 아닌 index값을 하나 키워서 다음 값으로 이동하는 식으로 하는 것이다.

메모리는 엄청나게 먹겠지만 시간적으로는 더 빠른 방법이다.