[백준 20058번] [Kotlin] 마법사 상어와 파이어스톰

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

20058번: 마법사 상어와 파이어스톰

 

난이도 : 골드 3
태그 : 구현, 그래프 이론, 그래프 탐색, 너비우선탐색, 시뮬레이션, 깊이우선탐색

 

 

1. 설명

삼성 기출 문제로 유명한 마법사 상어 시리즈 중 '마법사 상어와 파이어스톰' 문제입니다.

 

시뮬레이션 문제로써,

1. 파이어스톰을 n번 시전

2. 모든 파이어스톰 시전 후 가장 큰 덩어리 찾기

크게 두 파트로 나눌 수 있습니다.

파이어스톰 시전 과정은 단순 구현이지만

모든 파이어스톰을 시전한 후 가장 큰 덩어리를 찾는 과정에서는 DFS 혹은 BFS가 필요합니다.

 

 

 

 

2. 소스코드

 

2.1. 파이어스톰 - 시계 방향 회전

      

      

      

    
    

      <kotlin />
    
 for (i in 0 until n) {
        for (j in 0 until n) {
            copiedMap[i][j] = arr[n - 1 - j][i]
        }
    }

 

맵을 시계방향 회전하는 것은 위와 같이 단순하게 구현할 수 있습니다.

 

2^n 크기의 맵을 시계 방향으로 회전하는 부분입니다.

결과용 맵으로 쓸 copiedMap을 하나 생성해놓아야 합니다.

그냥 원본 맵을 그대로 회전하게 될 경우, 이전에 회전된 결과값을 또 다시 회전시킬 수 있기 때문입니다.

 

하지만, 해당 문제에서는 2^n 크기로 맵 구역을 나누고, 모든 구역을 시계방향으로 회전시켜야 하기에, 조금 변형을 줄 수 있겠습니다.

 

 

 

 

      

      

      

    
    

      <kotlin />
    
val copiedMap = Array(squareN) { Array(squareN) { 0 } }

for (startX in 0 until squareN step size) {
    for (startY in 0 until squareN step size) {
        for (i in 0 until size) {
            for (j in 0 until size) {
                copiedMap[i + startX][j + startY] = map[size - 1 - j + startX][i + startY]
            }
        }
    }
}

 

참고 - squaureN은 n * n, size는 마법사 상어가 파이어 스톰을 시전한 단계, 2^L1 입니다.

 

코틀린에서 step은 C/자바의 for문에서 for(int i = 0; i<n; i+= size) 중, i+=size에 대응된다고 볼 수 있습니다.

startX, startY가 0부터 squreN ( =n*n)을 size 만큼 증가시키면서,

모든 구역에 대해 시계방향 회전을 수행합니다.

 

 

 

2.2. 파이어스톰 : 얼음이 3개 이상 접해있지 않은 칸 찾기

      

      

      

    
    

      <kotlin />
    
val minus = Array(squareN) { Array(squareN) { false } }

repeat(squareN) { x ->
    repeat(squareN) { y ->
        var cnt = 0

        for (i in 0 until 4) {
            val nx = x + dx[i]
            val ny = y + dy[i]

            if (nx !in 0 until squareN || ny !in 0 until squareN || copiedMap[nx][ny] == 0) continue
            cnt++
        }

        if (cnt < 3) minus[x][y] = true
    }
}

repeat(squareN) { x ->
    repeat(squareN) { y ->
        map[x][y] = copiedMap[x][y]
        if (minus[x][y] && map[x][y] > 0) map[x][y]--
    }
}

 

저 같은 경우는 얼음이 3개 이상 접해있지 않은 곳을 체크하기 위해 2차원 boolean 배열을 사용했는데요.

동서남북 4방향의 얼음을 카운트하고 3 미만이면 1씩 감소시킵니다.

 

 

2.3. DFS : 가장 큰 얼음 덩어리 찾기

      

      

      

    
    

      <kotlin />
    
var cnt = 0
var max = 0


fun main()
-- 코드 생략 --

repeat(squareN) { x ->
    repeat(squareN) { y ->
        dfs(x, y)
        cnt = 0
    }
}
    
-- 코드 생략 --
}



fun dfs(x: Int, y: Int) {
    if (map[x][y] == 0 || visited[x][y]) return
    visited[x][y] = true
    cnt++
    max = maxOf(max, cnt)

    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx !in 0 until squareN || ny !in 0 until squareN) continue

        dfs(nx, ny)
    }
}

 

모든 파이어스톰 시전이 끝나면, 가장 큰 덩어리를 찾아야 하는데요.

이는 간단하게 dfs 혹은 bfs를 사용하여 구하면 됩니다.

 

cnt는 한 덩어리가 얼마나 큰지 확인할 변수,

max는 가장 큰 덩어리의 크기를 저장할 변수입니다.

 

모든 정점에서 dfs를 수행하면서,

얼음이 아닌 곳(map[x][y] == 0) 혹은 이미 방문한 정점(visited[x][y] == true) 이라면 return을 통해 빠져나오고,

한 덩어리를 탐색할 때 마다 cnt를 1씩 증가시키며, 매번 max를 최댓값으로 갱신합니다.

 

 

 

 

2.4. 전체 소스코드

      

      

      

    
    

      <kotlin />
    
import java.util.StringTokenizer
import kotlin.math.pow

val dx = arrayOf(1, -1, 0, 0)
val dy = arrayOf(0, 0, 1, -1)

lateinit var visited: Array<Array<Boolean>>
lateinit var map: Array<Array<Int>>
var max = 0
var squareN = 0
var cnt = 0

fun main() = with(System.`in`.bufferedReader()) {
    val (n, q) = readLine().split(" ").map { it.toInt() }
    squareN = 2.0.pow(n).toInt()

    map = Array(squareN) {
        val st = StringTokenizer(readLine())
        Array(squareN) { st.nextToken().toInt() }
    }

    val st = StringTokenizer(readLine())
    while (st.hasMoreTokens()) {
        val l = st.nextToken().toInt()

        val size = 2.0.pow(l).toInt()

        val copiedMap = Array(squareN) { Array(squareN) { 0 } }

        for (startX in 0 until squareN step size) {
            for (startY in 0 until squareN step size) {
                for (i in 0 until size) {
                    for (j in 0 until size) {
                        copiedMap[i + startX][j + startY] = map[size - 1 - j + startX][i + startY]
                    }
                }
            }
        }

        val minus = Array(squareN) { Array(squareN) { false } }

        repeat(squareN) { x ->
            repeat(squareN) { y ->
                var cnt = 0

                for (i in 0 until 4) {
                    val nx = x + dx[i]
                    val ny = y + dy[i]

                    if (nx !in 0 until squareN || ny !in 0 until squareN || copiedMap[nx][ny] == 0) continue
                    cnt++
                }

                if (cnt < 3) minus[x][y] = true
            }
        }

        repeat(squareN) { x ->
            repeat(squareN) { y ->
                map[x][y] = copiedMap[x][y]
                if (minus[x][y] && map[x][y] > 0) map[x][y]--
            }
        }
    }

    visited = Array(squareN) { Array(squareN) { false } }

    val sum = map.sumOf { it.sum() }
    repeat(squareN) { x ->
        repeat(squareN) { y ->
            dfs(x, y)
            cnt = 0
        }
    }
    println("$sum\n$max")
}

fun dfs(x: Int, y: Int) {
    if (map[x][y] == 0 || visited[x][y]) return
    visited[x][y] = true
    cnt++
    max = maxOf(max, cnt)

    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx !in 0 until squareN || ny !in 0 until squareN) continue

        dfs(nx, ny)
    }
}

 

 

 

 

3. 후기

다소 복잡한 시뮬레이션 문제였으나,

천천히 차근차근 요구사항에 맞게 구현해보니, 그리 어렵지 않게 풀 수 있었습니다.

삼성 기출문제 중 하나던데, 이런 문제만 나왔으면 좋겠네요 ㅎㅎ....