[코틀린] 백준 14052번: 연구소 - 삼성 SW 역량 테스트 기출 문제 풀이 및 효율성 팁
풀이
저번에 포스팅했던 감시 문제와 비슷하지만 좀 더 쉽다고 볼 수 있는 문제입니다.
삼성 기출을 풀때는 문제를 꼼꼼히 읽고, 제시하는 내용이 무엇인지 파악한 후, 세부 단계로 나눠서 차근차근 해결해 나가는 것이 중요합니다.
또한 시간 제한이 널널한 편이기 때문에 주먹구구식으로 푸는 것도 나쁘지 않습니다.
이 문제는 백트래킹을 활용해서 3개의 벽을 모든 경우의 수에 두고, BFS를 수행하여 바이러스를 퍼뜨린 뒤, 안전지대 범위를 계산하면 되는 문제입니다.
1. 백트래킹을 활용하여 모든 경우를 완전탐색 한다.
가로 세로의 범위가 (3 ≤ N, M ≤ 8) 이므로 백트래킹
을 시도해볼 수 있습니다. 2차원 배열에서 벽 3개를 설치할 수 있는 경우를 모두 구해주는 것입니다. 한 가지 팁을 드리자면 벽을 설치하는 순서는 중요하지 않으므로 중복 없는 조합을 구해주셔야 합니다.
(0, 1)에 위치에 벽을 설치한 후 (0, 2)위치에 벽을 설치 하는 것과, (0, 2)에 위치에 벽을 설치한 후 (0, 1)위치에 벽을 설치 하는 것은 아무 의미가 없이 다 똑같은 의미겠죠?
중복을 허용한 조합을 사용한 경우
fun permutation(depth: Int) {
if (depth == 3) {
// 3. 벽 3개를 다 세웠다면, 이제 바이러스를 퍼뜨려서 안전지대의 개수를 구해보자.
var countVirusRange = 0
val q: Queue<Virus> = LinkedList<Virus>(virus)
val check = Array(map.size) { BooleanArray(map[0].size) }
while (!q.isEmpty()) {
countVirusRange += spreadVirus(q.poll(), check)
}
answer = max(answer, max - countVirusRange)
return
}
for (y in map.indices) {
for (x in map[0].indices) {
if (isVisited[y][x] || map[y][x] != 0) continue
isVisited[y][x] = true // 중복 방지 방문처리
map[y][x] = 1 // 벽 세우기
max--
permutation(depth + 1)
isVisited[y][x] = false // 백트래킹: 원상복귀
map[y][x] = 0
max++
}
}
}
중복을 허용한 조합을 사용하게 된다면 위 사진과 같이 302212KB의 메모리, 932ms의 시간을 잡아먹습니다.
그러면 중복 허용하지 않는 조합을 사용한다면 어떻게 될까요?
중복을 허용하지 않는 조합을 사용하는 경우
fun permutation(depth: Int, startX: Int, startY: Int) {
if (depth == 3) {
// 3. 벽 3개를 다 세웠다면, 이제 바이러스를 퍼뜨려서 안전지대의 개수를 구해보자.
var countVirusRange = 0
val q: Queue<Virus> = LinkedList<Virus>(virus)
val check = Array(map.size) { BooleanArray(map[0].size) }
while (!q.isEmpty()) {
countVirusRange += spreadVirus(q.poll(), check)
}
answer = max(answer, max - countVirusRange)
return
}
for (y in startY until map.size) {
var new_x = 0
// 2차원 배열에서의 중복 없는 조합
if (startY == y) {
new_x = startX
} else {
new_x = 0
}
for (x in new_x until map[0].size) {
if (isVisited[y][x] || map[y][x] != 0) continue
isVisited[y][x] = true // 중복 방지 방문처리
map[y][x] = 1 // 벽 세우기
max--
permutation(depth + 1, x + 1, y)
isVisited[y][x] = false // 백트래킹: 원상복귀
map[y][x] = 0
max++
}
}
}
차이가 느껴지시나요? 백트래킹을 이용해 완전탐색을 하실 때, 순서가 중요하지 않다면 위와 같이 가지치기를 하여 더 효율적인 코드를 작성하실 수 있습니다.
2. 바이러스 전파
1 단계에서 세운 3개의 벽을 포함시켜서 각각의 바이러스를 전파하는 단계입니다. 반환 값은 바이러스 1개가 전파한 범위가 되겠네요.
fun spreadVirus(virus: Virus, check: Array<BooleanArray>): Int {
var countVirusRange = 0
val q: Queue<Virus> = LinkedList<Virus>()
q.offer(Virus(virus.x, virus.y))
check[virus.y][virus.x] = true
while (!q.isEmpty()) {
val cur = q.poll()
for (i in 0 until 4) {
val nx = cur.x + dx[i]
val ny = cur.y + dy[i]
if (nx < 0 || nx >= map[0].size || ny < 0 || ny >= map.size || check[ny][nx] || map[ny][nx] != 0) continue
countVirusRange++
check[ny][nx] = true
q.offer(Virus(nx, ny))
}
}
return countVirusRange
}
Source Code
package 삼성SW역량테스트.`14052번_연구소`
import java.util.*
import kotlin.math.max
private lateinit var map: Array<IntArray>
private lateinit var isVisited: Array<BooleanArray>
private val virus: Queue<Virus> = LinkedList<Virus>()
private var dy = arrayOf(-1, 0, 1, 0) // 상하좌우 방향정보
private var dx = arrayOf(0, 1, 0, -1)
private var max = 0
private var answer = Integer.MIN_VALUE
fun main() {
val (N, M) = readln().split(" ").map { it.toInt() }
map = Array(N) { IntArray(M) }
isVisited = Array(N) { BooleanArray(M) }
max = N * M // max = 맵의 전체 크기 - 벽 - 바이러스
// 1. 입력 데이터 받기
for (i in 0 until N) {
val st = StringTokenizer(readln())
for (j in 0 until M) {
map[i][j] = st.nextToken().toInt()
if (map[i][j] == 0) continue
max--
if (map[i][j] == 2) {
virus.offer(Virus(j, i))
}
}
}
// 2. 벽 세우기: 백트래킹으로 모든 경우를 따져봐야 함.
permutation(0, 0, 0)
println(answer)
}
fun permutation(depth: Int, startX: Int, startY: Int) {
if (depth == 3) {
// 3. 벽 3개를 다 세웠다면, 이제 바이러스를 퍼뜨려서 안전지대의 개수를 구해보자.
var countVirusRange = 0
val q: Queue<Virus> = LinkedList<Virus>(virus)
val check = Array(map.size) { BooleanArray(map[0].size) }
while (!q.isEmpty()) {
countVirusRange += spreadVirus(q.poll(), check)
}
answer = max(answer, max - countVirusRange)
return
}
for (y in startY until map.size) {
var new_x = 0
// 2차원 배열에서의 중복 없는 조합
if (startY == y) {
new_x = startX
} else {
new_x = 0
}
for (x in new_x until map[0].size) {
if (isVisited[y][x] || map[y][x] != 0) continue
isVisited[y][x] = true // 중복 방지 방문처리
map[y][x] = 1 // 벽 세우기
max--
permutation(depth + 1, x + 1, y)
isVisited[y][x] = false // 백트래킹: 원상복귀
map[y][x] = 0
max++
}
}
}
fun spreadVirus(virus: Virus, check: Array<BooleanArray>): Int {
var countVirusRange = 0
val q: Queue<Virus> = LinkedList<Virus>()
q.offer(Virus(virus.x, virus.y))
check[virus.y][virus.x] = true
while (!q.isEmpty()) {
val cur = q.poll()
for (i in 0 until 4) {
val nx = cur.x + dx[i]
val ny = cur.y + dy[i]
if (nx < 0 || nx >= map[0].size || ny < 0 || ny >= map.size || check[ny][nx] || map[ny][nx] != 0) continue
countVirusRange++
check[ny][nx] = true
q.offer(Virus(nx, ny))
}
}
return countVirusRange
}
data class Virus(val x: Int, val y: Int)
Author And Source
이 문제에 관하여([코틀린] 백준 14052번: 연구소 - 삼성 SW 역량 테스트 기출 문제 풀이 및 효율성 팁), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@blucky8649/코틀린-백준-15683번-감시-삼성-SW-역량-테스트-기출-문제-풀이-및-효율성-팁저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)