💡[BOJ 21608 / 코틀린] 상어 초등학교 - 구현

백준 21608_상어 초등학교 | 문제 링크

특별한 알고리즘이 아닌 단순한 구현 문제입니다.

 

문제 설명

N*N 교실에 1번부터 N²번까지의 학생이 한 자리씩 앉습니다.

각 학생의 친한 친구 4명씩을 사전 조사를 통해 파악해놨습니다.

각 학생의 만족도 총합이 가장 큰 좌석 배치 방법을 구하시오.

 

• 근처에 친한 친구가 0명이면 만족도는 0이고, 1명이면 1, 2명이면 10, 3명이면 100, 4명이면 1000이다.
• '근처, 인접'은 사방(四方)을 이야기한다.
• 규칙의 순서는 다음과 같다.

1. 빈 칸 중 친구가 인접한 칸이 가장 많은 칸으로 자리를 정한다.

2. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중 빈 칸이 가장 많은 칸으로 자리를 정한다.

3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

입력

첫째 줄에 N이 주어진다. 둘째 줄부터 N2개의 줄에 학생의 번호와 그 학생이 좋아하는 학생 4명의 번호가 한 줄에 하나씩 선생님이 자리를 정할 순서대로 주어진다.

학생의 번호는 중복되지 않으며, 어떤 학생이 좋아하는 학생 4명은 모두 다른 학생으로 이루어져 있다. 입력으로 주어지는 학생의 번호, 좋아하는 학생의 번호는 N2보다 작거나 같은 자연수이다. 어떤 학생이 자기 자신을 좋아하는 경우는 없다.

 

입력예

출력

첫째 줄에 학생의 만족도의 총 합을 출력한다.

출력예

 

main 함수

// classroom은 N by N (0 ~ N-1)
// table은 N*N by 5
fun main() {
    val sc = Scanner(System.`in`)
    val N = sc.nextInt()
    val classroom = Array(N) { Array(N) {0} }	// 1
    val table = Array(N * N) { Array(5) {0} }	// 2
    var satisfaction = 0
    for (i in 0 until N * N) {
        for (j in 0 until 5) {
            table[i][j] = sc.nextInt()
        }
    }
    for (i in 0 until N * N) {
        arrange(classroom, table[i], N)	// 3
    }
    for (i in 0 until N) {
        for (j in 0 until N) {
            var k = 0
            while (table[k][0] != classroom[i][j]) k++
            val info = table[k]
            satisfaction += satisfy(classroom, info, i, j, N)	// 4
        }
    }
    println(satisfaction)
}

1. classroom은 N * N 이차원 Int배열
2. table은 N² * 5 이차원 배열
   - 인덱스는 처리 순서입니다
   - 각 행의 0열은 배치할 학생의 번호(1~N²)입니다.
   - 각 행의 1~4열은 해당 학생의 친한 친구 4명입니다.
3. arrange 함수는 table[i] 배열의 0열 원소 학생을 classroom에 규칙에 맞게 배치시키는 함수입니다.
4. satisfy 함수는 classroom의 i행 j열에 있는 학생의 만족도를 반환합니다.

arrange 함수

fun arrange(classroom:Array<Array<Int>>, info:Array<Int>, N:Int) {
	val a = one(classroom, info, N)	// 1
	if (a.size != 1) two(classroom, a, N)	// 2
	if (a.size != 1) three(a)	// 3

	val i = a[0].first
	val j = a[0].second
	classroom[i][j] = info[0]	// 4
	return
}

1. one 함수는 info[0] 학생을 1번 규칙에 따라 배치시킬 수 있는 모든 좌표(Pair<Int, Int>)의 리스트(ArrayList)를 반환합니다.
2. 위의 경우의 수가 한가지가 아닐 경우, two 함수는 2번 규칙에 따라 배치시킬 수 있는 모든 좌표의 리스트를 반환합니다.
3. 위의 경우의 수가 한가지가 아닐 경우, three 함수는 3번 규칙에 따라 배치시킵니다.
4. 위 1,2,3 과정을 거치면 리스트 a의 원소는 하나만 남으므로 classroom에 학생을 배치시킵니다.

one 함수

fun one(classroom:Array<Array<Int>>, info:Array<Int>, N:Int):ArrayList<Pair<Int, Int>> {
	var ret = ArrayList<Pair<Int, Int>>()	// 1
	var nearFriends = 0	// 1
	for (i in 0 until N) {
		for (j in 0 until N) {
			var eachNearFriends = 0
			if (classroom[i][j] != 0) continue	// 2
			if (i > 0 && info.contains(classroom[i - 1][j])) eachNearFriends++	// 3
			if (i < N - 1 && info.contains(classroom[i + 1][j])) eachNearFriends++
			if (j > 0 && info.contains(classroom[i][j - 1])) eachNearFriends++
			if (j < N - 1 && info.contains(classroom[i][j + 1])) eachNearFriends++
			nearFriends = if (nearFriends >= eachNearFriends) nearFriends else eachNearFriends	// 4
		}
	}
	for (i in 0 until N) {
		for (j in 0 until N) {
			var eachNearFriends = 0
			if (classroom[i][j] != 0) continue
			if (i > 0 && info.contains(classroom[i - 1][j])) eachNearFriends++
			if (i < N - 1 && info.contains(classroom[i + 1][j])) eachNearFriends++
			if (j > 0 && info.contains(classroom[i][j - 1])) eachNearFriends++
			if (j < N - 1 && info.contains(classroom[i][j + 1])) eachNearFriends++
			if (nearFriends == eachNearFriends) ret.add(Pair(i, j))	// 5
		}
	}
	return ret	// 6
}

one 함수는 classroom을 두 번 탐색합니다.

1. 좌표의 리스트를 담아 반환할 return 변수, 해당 학생(info[0])의 친구가 가장 많이 인접한 자리의 인접 친구 수 nearFriends 변수를 선언합니다.
2. 좌석이 이미 차있을 시 조회하지 않습니다.
3. classroom[i][j] 좌석의 상,하,좌,우에 해당 학생의 친구가 있는지 확인하고 있으면 each 변수를 1 증가시킵니다.
4. each 변수(각 자리의 주변 친구 수)가 nearFriends 변수(전체 맵에서 최대 인접 친구 수)보다 크면 nearFriends 변수를 업데이트합니다.
5. (classroom 두번째 탐색) 위에서 구한 nearFriends 변수와 each 변수가 같은 모든 좌표를 ret에 추가합니다.
6. 전체 맵에서 info[0]의 친구가 가장 많이 인접한 좌석 좌표의 리스트를 반환합니다.

two

fun two(classroom:Array<Array<Int>>, a:ArrayList<Pair<Int, Int>>, N:Int) {
	var Empty = 0
	for (t in a.indices) {
		var eachEmpty = 0
		val i = a[t].first
		val j = a[t].second

		if (i > 0 && classroom[i - 1][j] == 0) eachEmpty++
		if (i < N - 1 && classroom[i + 1][j] == 0) eachEmpty++
		if (j > 0 && classroom[i][j - 1] == 0) eachEmpty++
		if (j < N - 1 && classroom[i][j + 1] == 0) eachEmpty++

		Empty = if (Empty >= eachEmpty) Empty else eachEmpty
	}
	for (t in a.size - 1 downTo 0) {
		var eachEmpty = 0
		val i = a[t].first
		val j = a[t].second

		if (i > 0 && classroom[i - 1][j] == 0) eachEmpty++
		if (i < N - 1 && classroom[i + 1][j] == 0) eachEmpty++
		if (j > 0 && classroom[i][j - 1] == 0) eachEmpty++
		if (j < N - 1 && classroom[i][j + 1] == 0) eachEmpty++
		if (Empty > eachEmpty) a.removeAt(t)
	}
}

위 one의 size가 1개가 아니면 실행하여 2번 조건에 따라 차출해내는 two 함수입니다. 자세한 로직은 one과 동일하므로 생략합니다.(두 번 탐색, each 변수 사용)

※ remove 할 시 뒤에서부터 탐색하는 이유 => 앞에서부터 탐색하다가 remove하면 인덱스가 하나씩 끌려오므로 탐색하지 못하는 값, 잘못 remove하는 값이 생기고 결국엔 indexOutOfBoundsException이 뜨게 됩니다.

 

three

fun three(a:ArrayList<Pair<Int, Int>>) {
	var iMin = Int.MAX_VALUE
	for (t in a.indices) {
		iMin = if (iMin <= a[t].first) iMin else a[t].first
	}
	for (t in a.size - 1 downTo 0) {
		if (iMin != a[t].first) a.removeAt(t)	// 1
	}
	while (a.size != 1) {
		if (a[0].second > a[1].second) a.removeAt(0)	// 2
		else a.removeAt(1)
	}
}

위 two의 size가 1이 아니면 실행하여 좌표 하나만 남기는 three 함수입니다.

1. 뒤에서부터 조회하여 행 값이 최대가 아닌 좌표들을 솎아냅니다.
2. size가 1이 아니므로 a 리스트는 최종 상태를 제외하고 항상 두 개 이상의 원소를 가지고 있을 것이고, 따라서 a[0] 좌표와 a[1] 좌표의 열 값을 비교하여 하나만 남겼습니다.

 

satisfy 함수

fun satisfy(classroom:Array<Array<Int>>, info:Array<Int>, i:Int, j:Int, N:Int):Int {
	var nearFriends = 0
	if (i > 0 && info.contains(classroom[i - 1][j])) nearFriends++
	if (i < N - 1 && info.contains(classroom[i + 1][j])) nearFriends++
	if (j > 0 && info.contains(classroom[i][j - 1])) nearFriends++
	if (j < N - 1 && info.contains(classroom[i][j + 1])) nearFriends++
	when (nearFriends) {
		1 -> return 1
		2 -> return 10
		3 -> return 100
		4 -> return 1000
	}
	return 0
}

one에서 그랬듯 해당 자리의 nearFriends를 조사하여 when 구문을 통해 만족도를 반환하였습니다.

 

전체 코드

import java.util.*
import kotlin.collections.ArrayList

// classroom은 N by N (0 ~ N-1)
// table은 N*N by 5
fun main() {
	val sc = Scanner(System.`in`)
	val N = sc.nextInt()
	val classroom = Array(N) { Array(N) {0} }
	val table = Array(N * N) { Array(5) {0} }
	var satisfaction = 0
	for (i in 0 until N * N) {
		for (j in 0 until 5) {
			table[i][j] = sc.nextInt()
		}
	}
	for (i in 0 until N * N) {
		arrange(classroom, table[i], N)
	}
	for (i in 0 until N) {
		for (j in 0 until N) {
			var k = 0
			while (table[k][0] != classroom[i][j]) k++
			val info = table[k]
			satisfaction += satisfy(classroom, info, i, j, N)
		}
	}
	println(satisfaction)
}
fun arrange(classroom:Array<Array<Int>>, info:Array<Int>, N:Int) {
	val a = one(classroom, info, N)
	if (a.size != 1) two(classroom, a, N)
	if (a.size != 1) three(a)

	val i = a[0].first
	val j = a[0].second
	classroom[i][j] = info[0]
	return
}
fun one(classroom:Array<Array<Int>>, info:Array<Int>, N:Int):ArrayList<Pair<Int, Int>> {
	var ret = ArrayList<Pair<Int, Int>>()
	var nearFriends = 0
	for (i in 0 until N) {
		for (j in 0 until N) {
			var eachNearFriends = 0
			if (classroom[i][j] != 0) continue
			if (i > 0 && info.contains(classroom[i - 1][j])) eachNearFriends++
			if (i < N - 1 && info.contains(classroom[i + 1][j])) eachNearFriends++
			if (j > 0 && info.contains(classroom[i][j - 1])) eachNearFriends++
			if (j < N - 1 && info.contains(classroom[i][j + 1])) eachNearFriends++
			nearFriends = if (nearFriends >= eachNearFriends) nearFriends else eachNearFriends
		}
	}
	for (i in 0 until N) {
		for (j in 0 until N) {
			var eachNearFriends = 0
			if (classroom[i][j] != 0) continue
			if (i > 0 && info.contains(classroom[i - 1][j])) eachNearFriends++
			if (i < N - 1 && info.contains(classroom[i + 1][j])) eachNearFriends++
			if (j > 0 && info.contains(classroom[i][j - 1])) eachNearFriends++
			if (j < N - 1 && info.contains(classroom[i][j + 1])) eachNearFriends++
			if (nearFriends == eachNearFriends) ret.add(Pair(i, j))
		}
	}
	return ret
}
fun two(classroom:Array<Array<Int>>, a:ArrayList<Pair<Int, Int>>, N:Int) {
	var Empty = 0
	for (t in a.indices) {
		var eachEmpty = 0
		val i = a[t].first
		val j = a[t].second

		if (i > 0 && classroom[i - 1][j] == 0) eachEmpty++
		if (i < N - 1 && classroom[i + 1][j] == 0) eachEmpty++
		if (j > 0 && classroom[i][j - 1] == 0) eachEmpty++
		if (j < N - 1 && classroom[i][j + 1] == 0) eachEmpty++

		Empty = if (Empty >= eachEmpty) Empty else eachEmpty
	}
	for (t in a.size - 1 downTo 0) {
		var eachEmpty = 0
		val i = a[t].first
		val j = a[t].second

		if (i > 0 && classroom[i - 1][j] == 0) eachEmpty++
		if (i < N - 1 && classroom[i + 1][j] == 0) eachEmpty++
		if (j > 0 && classroom[i][j - 1] == 0) eachEmpty++
		if (j < N - 1 && classroom[i][j + 1] == 0) eachEmpty++
		if (Empty > eachEmpty) a.removeAt(t)
	}
}
fun three(a:ArrayList<Pair<Int, Int>>) {
	var iMin = Int.MAX_VALUE
	for (t in a.indices) {
		iMin = if (iMin <= a[t].first) iMin else a[t].first
	}
	for (t in a.size - 1 downTo 0) {
		if (iMin != a[t].first) a.removeAt(t)
	}
	while (a.size != 1) {
		if (a[0].second > a[1].second) a.removeAt(0)
		else a.removeAt(1)
	}
}
fun satisfy(classroom:Array<Array<Int>>, info:Array<Int>, i:Int, j:Int, N:Int):Int {
	var nearFriends = 0
	if (i > 0 && info.contains(classroom[i - 1][j])) nearFriends++
	if (i < N - 1 && info.contains(classroom[i + 1][j])) nearFriends++
	if (j > 0 && info.contains(classroom[i][j - 1])) nearFriends++
	if (j < N - 1 && info.contains(classroom[i][j + 1])) nearFriends++
	when (nearFriends) {
		1 -> return 1
		2 -> return 10
		3 -> return 100
		4 -> return 1000
	}
	return 0
}

다른거 테스트해보다가 괜히 다시 틀림..