[Swift] 백준 16234 - 인구 이동

문제

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

16234번: 인구 이동

 

내 풀이

1. 틀잡기

import Foundation

let input = readLine()!.split(separator:" ").map { Int(String($0))! }
let n = input[0], l = input[1], r = input[2]

var board:[[Int]] = []

var dx = [-1, 1, 0, 0]
var dy = [0, 0, -1, 1]
var nx = 0
var ny = 0

for _ in 0..<n {
  board.append(readLine()!.split(separator:" ").map { Int(String($0))! })
}
var visited = Array(repeating: Array(repeating: false, count: n), count: n)

- "인접한 칸"으로부터 상하좌우 좌표로 움직인다는 아이디어를 얻고 이동방향 배열을 선언해주었고, 

- 한번 연합으로 묶은 나라는 중복으로 묶으면 안되므로 한번 연합으로 들어왔는지를 체크하기 위한 visited 배열을 선언해주었다.

 

2. DFS/BFS? + BFS 코드

- 우선 문제 조건을 살펴보면 "하루동안 다음과 같이 진행된다" = 그래프 탐색을 한바퀴 돈다 로 해석할 수 있다.

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

- 모든 인접 노드를 탐색하는 문제이므로 DFS/BFS 어떤 방법을 쓰든 무관하다. 필자는 BFS를 사용해서 품

- 위를 차례대로 코드로 작성하면 아래와 같다.

var visited = Array(repeating: Array(repeating: false, count: n), count: n) //중복으로 연합으로 묶지 않기 위한 visited 배열

func bfs(_ i:Int, _ j:Int) -> Int {
  var q = [(i, j)]
  var union = [(i, j)] //연합된 나라 리스트

  var sum = board[i][j] // 연합된 나라의 인구수 총합
  visited[i][j] = true //맨 처음 시작점은 방문처리
  
  while !q.isEmpty {
    let (x, y) = q.removeFirst()

    for i in 0..<4 {
      nx = x + dx[i]
      ny = y + dy[i]

      if 0..<n ~= nx && 0..<n ~= ny && l...r ~= abs(board[nx][ny] - board[x][y]) && !visited[nx][ny] {
        visited[nx][ny] = true
        sum += board[nx][ny]
        union.append((nx, ny))
        q.append((nx, ny))
      }
    }
  }

  let unionPeopleCount = Int(floor(Double(sum) / Double(union.count))) //연합된 나라는 모두 (총합 / 연합 수)이며 소수점은 버림
  for (i, j) in union {
    board[i][j] = unionPeopleCount
  }
  
  return union.count
}

 

3. "인구 이동이 더이상 발생하지 않을 때"를 어떻게 알고, 또 며칠간 발생하는지를 구할 수 있을까?

- BFS 코드는 이렇게 짰는데, 위 조건을 어떻게 알고 또 어떻게 알아낼 수 있을지에 대해서 아이디어가 도저히 안떠올라서 풀이를 참고했다.

- 만약 탐색을 한바퀴 돌고나서 "연합된 인구가 단 하나라면, 인구이동이 발생하지 않은것" 이므로, 1보다 클 때에만 인구이동이 발생한 날짜를 증가시키면 된다.

- 그리고 인구이동이 발생하지 않았다면, 더이상 인구이동을 진행하지 않으므로 반복문을 탈출한다.

var answer = 0 // 며칠동안 인구이동이 발생했는가

while true {
  visited = Array(repeating: Array(repeating: false, count: n), count: n) //다시 연합으로 묶는 루프를 실행해야하므로 visited 초기화해야함
  var flag = false //인구 이동이 발생했는지에 대한 플래그 변수
  for i in 0..<n {
    for j in 0..<n {
      if !visited[i][j] {
        if bfs(i, j) > 1 {
          flag = true
        }
      }
    }
  }

  if !flag { break } //인구이동이 발생하지 않았다면 반복문 멈춰!
  answer += 1
}

print(answer)

 

어떻게 접근해야하는지까진 아이디어를 얻었는데 3번에서 막혔다 ㅜ ㅜ 알고리즘 더 열심히 풀어야지..!