백준 1780번: 종이의 개수 (Kotlin)

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

1780번: 종이의 개수

 

풀이

NxN 행렬에서 숫자가 모두 같으면 해당 숫자를 카운트, 그렇지 않으면 크기를 9등분해서 각 행렬에 대해 같은 작업을 반복하는 문제였다. 분할 정복 or 재귀를 사용한다는 건 금방 알 수 있었지만 행렬을 나누는 게 어렵게 느껴졌다. 

 

행렬은 어떻게 표현하느냐에 따라 나누는 방법이 달라진다.

행렬은 어떻게 표현하는 게 좋을까? 나같은 경우 한 점과 길이로 구분하는 것이 가장 쉽다고 느꼈다.

행렬 표현

 

모두 정사각 행렬이기 때문에, 이렇게 시작 점과 길이를 알면 행렬을 간단하게 나타낼 수 있다.

 

그리고 점과 길이를 안다면 (점 + 길이)로 다른 행렬의 시작점을 계산하여 쉽게 분할할 수 있다.

행렬 분할

 

그러면 이제 큐or 스택과 같은 자료구조를 이용하는 반복문이나, 재귀 함수를 작성해서 답을 구할 수 있다.

 

행렬이 모두 같은 원소를 갖으면 해당 숫자를 카운트하고 분할을 종료한다. 만약 길이가 1일 경우, 원소가 하나라서 항상 같은 원소를 갖고 있므로 분할은 자동 종료된다.

 

리뷰

처음엔 왼쪽 끝의 좌표와 오른쪽 끝의 좌표를 사용해서 행렬을 구분하려고 했는데, 좌표를 구하는 연산 과정이 복잡해져서 멘붕이 왔었다..ㅋㅋㅋ

 

두 점으로 행렬을 구분하기 위해서는, 그림처럼 서로 다른 18개의 점을 구해야 한다. 그리고 다음 행렬의 좌표는 이전의 행이나 열에 +1을 해줘야 한다. 이처럼 그림 없이는 헷갈릴 수가 있는데, 머리로만 하려고 했던 게 가장 큰 문제였다.

 

적극적으로 문제를 풀어주자!!

 

나중에 멘탈을 다잡고 그림을 보며 위의 방식으로 해봤는데 결과는 시간초과 였다ㅋㅋ;;

 

 

코드1 (재귀 사용)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val matrix = Array(n) {
        val st = StringTokenizer(readLine())
        IntArray(n) { st.nextToken().toInt() }
    }

    val countArray = IntArray(3) // -1, 0, 1을 인덱스 0,1,2로 카운트
    countPapers(matrix, 0, 0, n, countArray)
    val answer = StringBuilder().append(countArray[0]).appendLine()
        .append(countArray[1]).appendLine()
        .append(countArray[2])
    print(answer)
}

// 인자: (행렬, 시작 행, 시작 열, 길이, 카운트 배열)
fun countPapers(matrix: Array<IntArray>, row: Int, col: Int, size: Int, countArray: IntArray) {
    val result = hasSame(matrix, row, col, size) // 같은 숫자만 갖고 있으면 해당 숫자를, 아니면 2를 반환

    // 같은 숫자만 갖고 있으면, 카운트 하고 분할 종료
    if (result != 2) {
        countArray[result + 1]++
        return
    }

    val dividedSize = size / 3
    // 0행 분할
    countPapers(matrix, row, col, dividedSize, countArray) // 0행 0열 (왼쪽 위 행렬)
    countPapers(matrix, row, col + dividedSize, dividedSize, countArray) // 0행 1열 (중앙 위)
    countPapers(matrix, row, col + 2 * dividedSize, dividedSize, countArray) // 0행 2열 (오른쪽 위)

    // 1행
    countPapers(matrix, row + dividedSize, col, dividedSize, countArray)
    countPapers(matrix, row + dividedSize, col + dividedSize, dividedSize, countArray)
    countPapers(matrix, row + dividedSize, col + 2 * dividedSize, dividedSize, countArray)

    // 2행
    countPapers(matrix, row + 2 * dividedSize, col, dividedSize, countArray)
    countPapers(matrix,row + 2 * dividedSize, col + dividedSize, dividedSize, countArray)
    countPapers(matrix, row + 2 * dividedSize, col + 2 * dividedSize, dividedSize, countArray)
}

fun hasSame(matrix: Array<IntArray>, startRow: Int, startCol: Int, size: Int): Int {
    val prevPaper = matrix[startRow][startCol]

    for (row in startRow until startRow + size) {
        for (col in startCol until startCol + size) {
            if (prevPaper != matrix[row][col]) {
                return 2 // 다른 숫자를 갖고 있으면 2를 반환한다
            }
        }
    }

    return prevPaper // 같은 숫자만 갖고 있으면, 해당 숫자 반환
}

 

코드2 (Queue 사용)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

data class MatrixInfo(val row: Int, val col: Int, val size: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val matrix = Array(n) {
        val st = StringTokenizer(readLine())
        IntArray(n) { st.nextToken().toInt() }
    }

    print(countPapers(matrix))
}

fun countPapers(matrix: Array<IntArray>): StringBuilder {
    val queue: Queue<MatrixInfo> = LinkedList()
    queue.offer(MatrixInfo(0, 0, matrix.size))

    val count = IntArray(3)

    while (queue.isNotEmpty()) {
        val matrixInfo = queue.poll()
        val result = hasSame(matrix, matrixInfo) // -1,0,1 -> 같은 숫자로 채워진 종이 , 2 -> 다른 숫자 포함

        if (result != 2) {
            count[result + 1]++
            continue
        }

        val row = matrixInfo.row
        val col = matrixInfo.col
        val dividedSize = matrixInfo.size / 3

        queue.offer(MatrixInfo(row, col, dividedSize)) // 0행 0열
        queue.offer(MatrixInfo(row, col + dividedSize, dividedSize)) // 0행 1열
        queue.offer(MatrixInfo(row, col + 2 * dividedSize, dividedSize)) // 0행 2열

        // 1행
        queue.offer(MatrixInfo(row + dividedSize, col, dividedSize))
        queue.offer(MatrixInfo(row + dividedSize, col + dividedSize, dividedSize))
        queue.offer(MatrixInfo(row + dividedSize, col + 2 * dividedSize, dividedSize))

        // 2행
        queue.offer(MatrixInfo(row + 2 * dividedSize, col, dividedSize))
        queue.offer(MatrixInfo(row + 2 * dividedSize, col + dividedSize, dividedSize))
        queue.offer(MatrixInfo(row + 2 * dividedSize, col + 2 * dividedSize, dividedSize))
    }

    return StringBuilder().append(count[0]).appendLine()
        .append(count[1]).appendLine()
        .append(count[2])
}

fun hasSame(matrix: Array<IntArray>, matrixInfo: MatrixInfo): Int {
    val prevPaper = matrix[matrixInfo.row][matrixInfo.col]

    for (row in matrixInfo.row until matrixInfo.row + matrixInfo.size) {
        for (col in matrixInfo.col until matrixInfo.col + matrixInfo.size) {
            if (prevPaper != matrix[row][col]) {
                return 2
            }
        }
    }

    return prevPaper
}

 

틀렸던 코드 (끝 점 2개로 행렬 구분) - 메모리 초과

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

// 왼쪽 위, 오른쪽 아래의 점으로 행렬을 구분한다
data class Points(val r1: Int, val c1: Int, val r2: Int, val c2: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val n = readLine().toInt()
    val matrix = Array(n){
        val st = StringTokenizer(readLine())
        IntArray(n) { st.nextToken().toInt() }
    }

    print(countPapers(matrix))
}

fun countPapers(matrix: Array<IntArray>): StringBuilder{
    val queue: Queue<Points> = LinkedList()
    queue.offer(Points(0,0, matrix.size-1, matrix.size-1))

    val count = IntArray(3)

    while (queue.isNotEmpty()) {
        val points = queue.poll()
        val result = hasSame(matrix, points)

        if (result != 2){
            count[result + 1]++
            continue
        }

        val r1 = points.r1; val c1 = points.c1
        val r2 = points.r2; val c2 = points.c2
        val gapR1 = r1 + (r2 - r1) / 3; val gapR2 = gapR1 + (r2 - r1) / 3 + 1 // 1/3, 2/3 지점
        val gapC1 = c1 + (c2 - c1) / 3; val gapC2 = gapC1 + (c2 - c1) / 3 + 1

        queue.offer(Points(r1, c1, gapR1, gapC1)) // 0행 0열
        queue.offer(Points(r1, gapC1 + 1, gapR1, gapC2)) // 0행 1열
        queue.offer(Points(r1, gapC2 + 1, gapR1, c2)) // 0행 2열

        queue.offer(Points(gapR1 + 1, c1, gapR2, gapC1))
        queue.offer(Points(gapR1 + 1, gapC1 + 1, gapR2, gapC2))
        queue.offer(Points(gapR1 + 1, gapC2 + 1, gapR2, c2))

        queue.offer(Points(gapR2 + 1, c1, r2, gapC1))
        queue.offer(Points(gapR2 + 1, gapC1 + 1, r2, gapC2))
        queue.offer(Points(gapR2 + 1, gapC2 + 1, r2, c2))
    }

    return StringBuilder().append(count[0]).appendLine()
            .append(count[1]).appendLine()
            .append(count[2])
}

fun hasSame(matrix: Array<IntArray>, points: Points): Int {
    val paper = matrix[points.r1][points.c1]

    for (row in points.r1..points.r2) {
        for (col in points.c1..points.c2){
            if (paper != matrix[row][col]) return 2
        }
    }

    return paper
}