백준 - 빙고(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/2578

 

[문제 설명]

숫자를 몇개 불렀을 때 빙고가 완성됐는지 묻는 문제.

 

[접근 방법]

처음엔 매번 가로 세로 대각선을 체크할까 고민했던 문제.

사실 그럴 필요는 없다.

 

각 가로줄은 5개의 체크가 필요하다

각 세로줄 또한 5개의 체크가 필요하다.

대각선 2개도 5개의 체크가 필요하다.

 

사회자가 숫자를 부를 때마다 해당 번호가 대각선에 포함되면 대각선의 체크 필요 개수를 줄이고, 가로줄과 세로줄의 체크 필요개수를 줄이면 된다.

 

 

 

위의 그림에서 3을 불렀으면 이제 2행(16,1,13,3,25)은 4개만 더 체크하면 된다.

4열(24,3,21,14,23)도 4개만 더 체크하면 된다.

이런 식으로 각 숫자를 체크할 때마다, 가로 세로의 필요 개수를 줄여주면 된다.

 

그렇다면 대각선은 어떻게 체크할까?

위를 보면 대각선의 좌표들은 (0,0) (1,1) (2,2)...(K,K)형태를 이루고 있다. 즉, y=x그래프 -> 행과 열의 값이 같으면 위 대각선에 속하는 것이다.

 

위 그래프는 (4,0), (3,1)...(K,-K+4) 형태. y = -x+4의 형태를 이루고 있다. 즉, 행과 열의 합이 4이면 이 대각선에 속한다.

 

[Kotlin 코드]

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    // key를 값 value를 좌표인 map을 만듬.
    val map = Array(26){IntArray(2)}
    // 세로 빙고를 만족하기 위해 필요한 체크 개수
    val sero = intArrayOf(5,5,5,5,5)
    // 가로 빙고를 만족하기 위해 필요한 체크 개수
    val garo = intArrayOf(5,5,5,5,5)
    // 좌상단에서 우하단으로 가는 빙고와, 우상단에서 좌하단으로 가는 빙고를 위해 필요한 체크 개수
    val daegaek = intArrayOf(5,5)
    // key를 블록의 값으로, value는 해당 블록의 좌표를 가르킨다.
    repeat(5) { row ->
        readLine().split(" ").map { it.toInt() }.forEachIndexed { col, num ->
            map[num][0] = row
            map[num][1] = col
        }
    }

    // 사회자가 부른 번호 개수
    var idxOfCall = 0
    // 현재 빙고의 개수
    var cntOfBingo = 0
    repeat(5) { row ->
        readLine().split(" ").map { it.toInt() }.forEach { calledNum ->
            idxOfCall++
            val position = map[calledNum]!!

            // (0,0), (1,1)처럼 같으면 대각 좌상단에서 우하단으로 가는 대각선임.
            if (position[0] == position[1]) {
                daegaek[0]--
                if (daegaek[0] == 0) {
                    cntOfBingo++
                }
            }
            // 두 좌표의 합이 4면 좌하단에서 우상단으로 가는 대각선임
            if (position[0] + position[1] == 4) {
                daegaek[1]--
                if (daegaek[1] == 0) {
                    cntOfBingo++
                }
            }

            // 세로와 가로 빙고 필요 개수를 줄여주고 빙고가 완성되면 빙고 개수를 추가함.
            --sero[position[1]]
            --garo[position[0]]
            if (sero[position[1]] == 0) {
                cntOfBingo++
            }
            if (garo[position[0]] == 0) {
                cntOfBingo++
            }

            // 빙고가 3개 이상 완료 되면 결과를 출력하고 프로그램 종료
            if (cntOfBingo >= 3) {
                println(idxOfCall)
                return
            }
        }
    }

    println(-1)
}