[BOJ 21608] 상어 초등학교 Kotlin

 

21608번: 상어 초등학교

 

 

문제

 

문제를 간략히 설명하면 다음과 같다.

 

선생님이 정한 학생의 순서와 각 학생이 좋아하는 학생에 대한 정보가 주어진다.

한 칸에는 학생 한 명의 자리만 있을 수 있고, | r1 - c1 | + | c1 - c2 | = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접하다고 한다.

즉, 상하좌우칸을 인접하다고 말하는 것이다.

학생의 자리를 정할 때는 지켜야 하는 규칙이 있다.

 

1.  비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
3. 2를 만족하는 칸도 여러 개인 경우에는  행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

위 규칙을 만족하는 자리에 학생들을 배치한 후 학생의 만족도를 구하기 위해 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 알아야 한다.

그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.

 

 

문제풀이

 

1. 비어있는 칸 구하기

 

먼저 main 함수를 살펴보자.

 

 

• num : 학생의 순서를 저장하는 배열
• info : 각 학생이 좋아하는 학생 정보를 저장하는 배열
• student : 학생들의 자리 배치 정보
• empty : 비어있는 칸을 저장하는 배열

 

배열 세팅이 끝났으면 제일 먼저 비어있는 칸의 수를 구한다. (init 함수)

그런 다음 정해진 순서에 따라 조건에 맞는 자리를 찾은 후 학생을 배치하고 student 배열과 empty 배열에 학생을 배치했다는 표시를 해준다.

그리고 그 자리와 인접한 자리의 비어있는 칸 수를 감소시킨다.

 

	private var n = 0
	private var num = intArrayOf()
	private var info = arrayOf<List<Int>>()
	private var student = arrayOf<IntArray>()
	private var empty = arrayOf<IntArray>()
	private val dx = arrayOf(-1, 0, 0, 1)
	private val dy = arrayOf(0, -1, 1, 0)
	fun main() = with(System.`in`.bufferedReader()) {
	n = readLine().toInt()
	num = IntArray(n * n) // 학생 순서
	info = Array<List<Int>>(n * n + 1) { listOf<Int>() } // 각 학생이 좋아하는 학생 정보
	student = Array(n) { IntArray(n) } // 자리
	empty = Array(n) { IntArray(n) } // 비어있는 칸
	for (i in 0 until n * n) {
	val input = readLine().split(" ").map { it.toInt() }
	num[i] = input[0]
	info[num[i]] = input.subList(1, 5)
	}
	init()
	for (i in num.indices) {
	var seat = findSeat(num[i])
	student[seat.first][seat.second] = num[i]
	empty[seat.first][seat.second] = -1
	for (i in dx.indices) {
	val nx = seat.first + dx[i]
	val ny = seat.second + dy[i]
	if (!isNotWall(nx, ny) || empty[nx][ny] < 0) continue
	empty[nx][ny]--
	}
	}
	println(satisfied())
	}

view raw [BOJ 21608] 상어 초등학교 main.kt hosted with ❤ by GitHub

 

init 함수를 통해 비어있는 칸을 구한다.

처음에는 4로 초기화하고 상하좌우 중에 벽이 있다면 비어있는 칸 수를 감소시킨다.

 

	private fun init() {
	for (i in empty.indices) {
	for (j in empty[i].indices) {
	empty[i][j] = 4;
	// 벽이 있는 경우
	if (i == 0 || i == n - 1) empty[i][j]--
	if (j == 0 || j == n - 1) empty[i][j]--
	}
	}
	}

view raw [BOJ 21608] 상어 초등학교 init.kt hosted with ❤ by GitHub

 

 

2. 자리 배치

 

(0, 0)부터 (n - 1, n -1)까지 학생이 배치되지 않은 자리, 즉 student[i][j]가 0인 자리를 확인한다.

현재 자리를 배치하려는 학생이 좋아하는 학생이 인접한 칸에 몇 명 있는지를 구하고 최댓값을 찾는다.

현재 칸에서 구한 좋아하는 학생 수가 최댓값과 같으면 후보 자리를 저장하는 list에 추가를 해주고 최댓값보다 크면 list를 비우고 최댓값을 갱신시킨다.

 

후보가 되는 자리를 모두 찾았다면 규칙을 만족하는 자리를 찾아야 한다.

1번 규칙을 만족하는 자리가 여러 개라면 인접한 칸 중에서 비어있는 칸의 수가 가장 많은 칸을 찾아야 하므로 empty 배열 값에 대해 내림차순으로 정렬해준다.

 

sortWith는 stable sort이고 자리를 찾을 때 행이 작은 순, 열이 작은 순으로 찾았기 때문에 3번 조건은 이미 만족되었다.

정렬 후 첫번째 자리가 바로 해당 학생이 앉을 자리가 된다.

 

	private fun findSeat(now : Int) : Pair<Int, Int> {
	var max = 0
	var list = mutableListOf<Pair<Int, Int>>()
	for (i in empty.indices) {
	for (j in empty[i].indices) {
	if (student[i][j] != 0) continue
	var likes = 0 // 인접한 칸에 있는 좋아하는 학생 수
	for (k in dx.indices) {
	val ni = i + dx[k]
	val nj = j + dy[k]
	if (!isNotWall(ni, nj)) continue
	if (info[now].contains(student[ni][nj])) likes++
	}
	if (max < likes) { // 최댓값을 갱신하면서 자리가 될 수 있는 후보도 갱신
	list.clear()
	list.add(Pair(i, j))
	max = likes
	} else if (max == likes) { // 최댓값과 같으면 추가
	list.add(Pair(i, j))
	}
	}
	}
	// 인접한 칸에 있는 좋아하는 학생 수가 동일한 자리가 있으면
	// 인접한 칸 중에서 비어있는 칸이 가장 많은 칸에 대해 내림차순으로 정렬
	// sortWith는 stable sort라 3번 조건은 유지됨
	list.sortWith(compareByDescending({ empty[it.first][it.second] }))
	return list[0]
	}

view raw [BOJ 21608] 상어 초등학교 자리 배치.kt hosted with ❤ by GitHub

 

 

3. 만족도 구하기

 

자리 배치가 모두 끝난 후에 각 칸의 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구하고 만족도를 계산해준다.

 

	private fun satisfied() : Int {
	var sum = 0
	for (i in student.indices) {
	for (j in student[i].indices) {
	var cnt = 0
	for (k in dx.indices) {
	val nx = i + dx[k]
	val ny = j + dy[k]
	if (!isNotWall(nx, ny)) continue
	// 해당 학생이 좋아하는 학생인 경우 cnt 증가
	if (info[student[i][j]].contains(student[nx][ny])) cnt++
	}
	if (cnt > 1) sum += Math.pow(10.toDouble(), (cnt - 1).toDouble()).toInt()
	else sum += cnt
	}
	}
	return sum
	}

view raw [BOJ 21608] 상어 초등학교 만족도.kt hosted with ❤ by GitHub

 

Kotlin 전체 코드

 

	private var n = 0
	private var num = intArrayOf()
	private var info = arrayOf<List<Int>>()
	private var student = arrayOf<IntArray>()
	private var empty = arrayOf<IntArray>()
	private val dx = arrayOf(-1, 0, 0, 1)
	private val dy = arrayOf(0, -1, 1, 0)
	fun main() = with(System.`in`.bufferedReader()) {
	n = readLine().toInt()
	num = IntArray(n * n) // 학생 순서
	info = Array<List<Int>>(n * n + 1) { listOf<Int>() } // 각 학생이 좋아하는 학생 정보
	student = Array(n) { IntArray(n) } // 자리
	empty = Array(n) { IntArray(n) } // 비어있는 칸
	for (i in 0 until n * n) {
	val input = readLine().split(" ").map { it.toInt() }
	num[i] = input[0]
	info[num[i]] = input.subList(1, 5)
	}
	init()
	for (i in num.indices) {
	var seat = findSeat(num[i])
	student[seat.first][seat.second] = num[i]
	empty[seat.first][seat.second] = -1
	for (i in dx.indices) {
	val nx = seat.first + dx[i]
	val ny = seat.second + dy[i]
	if (!isNotWall(nx, ny) || empty[nx][ny] < 0) continue
	empty[nx][ny]--
	}
	}
	println(satisfied())
	}
	private fun init() {
	for (i in empty.indices) {
	for (j in empty[i].indices) {
	empty[i][j] = 4;
	// 벽이 있는 경우
	if (i == 0 || i == n - 1) empty[i][j]--
	if (j == 0 || j == n - 1) empty[i][j]--
	}
	}
	}
	private fun findSeat(now : Int) : Pair<Int, Int> {
	var max = 0
	var list = mutableListOf<Pair<Int, Int>>()
	for (i in empty.indices) {
	for (j in empty[i].indices) {
	if (student[i][j] != 0) continue
	var likes = 0 // 인접한 칸에 있는 좋아하는 학생 수
	for (k in dx.indices) {
	val ni = i + dx[k]
	val nj = j + dy[k]
	if (!isNotWall(ni, nj)) continue
	if (info[now].contains(student[ni][nj])) likes++
	}
	if (max < likes) { // 최댓값을 갱신하면서 자리가 될 수 있는 후보도 갱신
	list.clear()
	list.add(Pair(i, j))
	max = likes
	} else if (max == likes) { // 최댓값과 같으면 추가
	list.add(Pair(i, j))
	}
	}
	}
	// 인접한 칸에 있는 좋아하는 학생 수가 동일한 자리가 있으면
	// 인접한 칸 중에서 비어있는 칸이 가장 많은 칸에 대해 내림차순으로 정렬
	// sortWith는 stable sort라 3번 조건은 유지됨
	list.sortWith(compareByDescending({ empty[it.first][it.second] }))
	return list[0]
	}
	private fun isNotWall(x : Int, y : Int) = x in 0 until n && y in 0 until n
	private fun satisfied() : Int {
	var sum = 0
	for (i in student.indices) {
	for (j in student[i].indices) {
	var cnt = 0
	for (k in dx.indices) {
	val nx = i + dx[k]
	val ny = j + dy[k]
	if (!isNotWall(nx, ny)) continue
	// 해당 학생이 좋아하는 학생인 경우 cnt 증가
	if (info[student[i][j]].contains(student[nx][ny])) cnt++
	}
	if (cnt > 1) sum += Math.pow(10.toDouble(), (cnt - 1).toDouble()).toInt()
	else sum += cnt
	}
	}
	return sum
	}

view raw [BOJ 21608] 상어 초등학교.kt hosted with ❤ by GitHub