PS 풀이 BOJ 27904 2025.09.05 6분

[백준 27904] 키파-틱택토

티어: 다1

이 문제의 가장 큰 특징이라면, 키파-틱택토의 규칙이 무려 1시간에 달하는 유튜브 영상으로, 심지어 음성으로 제공된다는 것이다.

그렇다고 1시간 중 일부만 들어도 되는 것도 아니다. 1시간 동안 쉼 없이 $n$ 행 $m$ 열에 대한 조건이 주어지고 그게 맞는지 아닌지에 따라서 누가 이기는지 정해진다.

일단 이 규칙들을 어떻게든 텍스트로 바꿔야, 이를 코드로 짤 수 있을 것이다. 1시간 동안 단 1개의 조건도 놓치지 않고 들어서 적는 건 너무 힘들다. 다행히도 좋은 STT(Speech to Text) 라이브러리가 많고 유튜브 자막도 충분히 훌륭하게 역할을 수행해내기 때문에, 이것들을 복사 붙여넣기 하는 것으로 1시간을 아낄 수 있다.

이제 자연어로 이루어진 조건들을, 어떻게든 코드로 바꿔야 한다. 나는 이런 방법을 사용했다.

우선, 조건 문장을 분석해보자. 모든 문장의 첫 단어는 '만일', '아니고', '아니라면' 이렇게 3가지 형태 중 하나이다.

각각 if, else if, else에 대응시킬 수 있다. 또한 '아니라면' 뒤에는 '~가 이겼습니다'가 반드시 온다는 사실도 알 수 있다.

문장의 끝 단어를 보면, '라면', '이겼습니다' 이렇게 2가지 형태 중 하나이다.

'라면'이 문장의 끝으로 오는 경우 그 문장의 첫 단어는 '만일' 혹은 '아니고'이다. 그리고 두 단어 사이에 조건이 존재한다.

'이겼습니다'가 문장의 끝으로 오는 경우, '이겼습니다' 바로 앞 단어가 '라면' 혹은 '아니라면'이다.

또한 '이겼습니다'의 경우 그 뒤에 더 이상 부속 조건이 없기 때문에, '이겼습니다'가 나오기 전까지 나온 선행 조건들을 만족시킬 때 ~가 이긴다는 것으로 해석할 수 있다. 뒤에 더 이상 부속 조건이 없다는 것에서 return의 사용 가능성을 볼 수 있다.

위 규칙을 통해 공백이나 문장부호 없이 정제된 텍스트에서 아래와 같은 규칙으로 '모두 바꾸기' 기능을 사용해 조건문을 만들 수 있다.

만일: if(board[
아니고: else if(board[
아니라면: else { return
행: ][
열이: ]=="
O라면: O") {
X라면: X") {
O가이겼습니다: "O" }
X가이겼습니다: "X" }

보드판의 상태를 나타내는 1-based 2차원 배열 board를 인자로 가지는 함수 check를 만들어서 저 조건문들을 넣으면 보드판에 모든 칸이 채워져 있는 경우인 서브태스크 2를 맞을 수 있다. 보드판에 빈칸이 없기 때문에 'HAVANA WINS'와 'KIPA WINS' 중에만 선택하면 된다.

서브태스크 3부터는 매우 힘들어진다. 보드판이 아직 다 채워지지 않은 경우에 '승리 선언'을 할 수 있는지 검사하기 위해 모든 경우에 대해 승리하는 사람이 정해져 있는지 체크해야 하기 때문이다. 에디토리얼을 봐도 이해가 쉽지 않다.

AC를 받기 위해선 올바른 출력을 하면서 동시에, 코드의 길이가 2023바이트 이하여야 한다. 에디토리얼에서는 조건문들을 python에서 zlib 등으로 압축해 저장하는 방법을 별해로 제시하고 있지만 python이 아니라면 이것도 쉽지 않을 것이다. 따라서 AC를 받으려면 서브태스크 5의 정해를 따라가야 한다고 판단해 이를 구현했다.

정해에서는 보드의 각 칸에 점수가 존재하며 게임의 승패는 이 점수의 총합으로 결정된다고 가정하면, 조건들을 통해 이 점수들을 실제로 알아낼 수 있다고 말하고 있다. 또한 에디토리얼을 계속 읽다 보면 이 점수가 1에서 32 사이의 서로 다른 정수 16개로 이루어져 있다는 사실도 알 수 있다.

python의 linprog 라이브러리를 사용하면 선형계획법 코드를 쉽게 짤 수 있다. 이것을 사용해보자.

우선, 앞서 만든 check 함수에 가능한 모든 완성된 보드판을 넣어서 그때의 결과를 저장한다. 경우의 수는 ${}_{16}\mathrm{C}_{8} = 12870$ 개로 그리 많지는 않다. 이제 모든 보드판과 결과에 대해, 아래 작업을 수행한다.

16차원 벡터 $c$ 를 만든다. 보드판을 가로로 읽어 읽은 순서대로 다시 재배열하면 길이가 16인 문자열로 바꿀 수 있다.

이제, 이 문자열에 대해

$i$ 번째 칸을 KIPA가 가져갔다면 $c[i] = 1$
$i$ 번째 칸을 HAVANA가 가져갔다면 $c[i] = -1$

이렇게 완성된 $c[i]$ 를 $A$ 배열에 저장하자.

이제 우리가 구하려는 실제 $i$ 번째 칸의 점수를 $w[i]$ 라고 하자. KIPA가 이긴 경우 수식은 다음과 같아야 한다.

\sum_{i=0}^{15} c_i \cdot w_i > 0

HAVANA가 이긴 경우는 다음과 같아야 한다.

\sum_{i=0}^{15} c_i \cdot w_i < 0

그러나 선형계획법에서 조건에 있는 부등식은 항상 등호를 포함해야 한다. 부등호의 방향이 다르면 불편하기에 통일해주는 것이 좋다. 다행히도 각 칸의 점수를 정수로 표현할 수 있다고 했기 때문에, 다음과 같이 식을 변형할 수 있다.

-\sum_{i=0}^{15} c_i \cdot w_i \leq -1

\sum_{i=0}^{15} c_i \cdot w_i \leq -1

전체 문제는 다음과 같이 정의할 수 있다.

A_i = \begin{cases} - c^{(i)} & \text{if KIPA wins on board } i \\ \;\;\;c^{(i)} & \text{if HAVANA wins on board } i \end{cases}

b_i = -1 \quad \text{(Always)}

\text{So,}

A = \begin{bmatrix} - c^{(1)} \\ c^{(2)} \\ \vdots \\ - c^{(n)} \end{bmatrix}, \quad b = \begin{bmatrix} -1 \\ -1 \\ \vdots \\ -1 \end{bmatrix}

\text{Find } w \in \mathbb{R}^{16} \text{ such that:}

A \cdot w \leq b

1 \leq w_i \leq 32 \quad \text{for } i = 0, 1, \ldots, 15

식으로 보면 많이 복잡해보이지만, 앞서 말한 linprog 라이브러리를 사용하면 매우 쉽게 구현할 수 있다. 아래는 예시 코드이다.

Python12 lines

def solve(A,b):
    res=linprog(
        c=np.zeros(16),
        A_ub=A,
        b_ub=b,
        bounds=[(1,32)]*16,
        method='highs'
    )
    if res.success:
        return res.x
    else:
        raise RuntimeError("망했어요")

이렇게 하면 마침내 각 칸에 있는 점수를 알 수 있다. bounds를 1부터 32로 제한했기 때문에, 에디토리얼에서 말한 1부터 32 사이의 서로 다른 정수 16개가 정확히 점수로 나온다.

이제 이를 알게 되었으니, '승리 선언' 여부와 실제 승/패를 판단하는 것은 지금까지에 비하면 매우 쉽다.

JavaScript72 lines

var [t,...s] = require('fs').readFileSync(0,'utf8').trim().split('\n')
s = s.map(e=>e.split('').map(f=>f=='X'?1:f=='.'?0:-1)) //미리 작업

function hab(v,a,b) {
    var c = 0
    for(var i = a; i <= b; i++) c+= v[i]
    return c
}
/*
각 칸의 점수를 jumsu 배열에 저장해 사용
jumsu 배열은 32P16(10^22)개의 경우의 수가 존재하므로 브루트포스는 의미가 없다.
*/
var jumsu = [ //검열됨
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,0],
    [0,0,0,0]
]
var dab = ''

var havana = 0 //HAVANA의 점수
var havanac = 0 //HAVANA가 지금까지 놓은 개수
var kipa = 0 //KIPA의 점수
var kipac = 0 //KIPA가 지금까지 놓은 개수
var turn = 0 //현재 턴
var bincan = [] //빈칸들의 점수를 저장

for(var i = 0; i < t; i++) {
    havana = 0
    havanac = 0
    kipa = 0
    kipac = 0
    bincan = []
    for(var k = 0; k < 4; k++) {
        for(var j = 0; j < 4; j++) {
            if(s[i*4+k][j] < 0) {
                havana += jumsu[k][j]
                havanac++
            }else if(s[i*4+k][j] > 0) {
                kipa += jumsu[k][j]
                kipac++
            }else {
                bincan.push(jumsu[k][j])
            }
        }
    }
    if(havanac + kipac == 16) { //모든 칸이 채워져있으면 바로 점수로 승리 판별
        dab += (havana>kipa?'HAVANA WINS\n':'KIPA WINS\n')
        continue
    }
    bincan.sort((a,b)=>a-b)
    //HAVANA가 가장 점수가 작은칸들만 가져가도 KIPA보다 점수가 높다면 승리 선언
    if(havana + hab(bincan,0,7-havanac) > kipa + hab(bincan,8-havanac,15-havanac-kipac)) {
        dab += 'HAVANA DECLARES A WIN\n'
        continue
    }
    //KIPA가 가장 점수가 작은칸들만 가져가도 HAVANA보다 점수가 높다면 승리 선언
    if(kipa + hab(bincan,0,7-kipac) > havana + hab(bincan,8-kipac,15-havanac-kipac)) {
        dab += 'KIPA DECLARES A WIN\n'
        continue
    }
    bincan.sort((a,b)=>b-a)
    turn = havanac <= kipac ? 1 : 0
    bincan.forEach(e=>{ //번갈아 가면서 점수가 높은 칸 부터 차지
        if(turn) havana+=e
        else kipa+=e
        turn = 1-turn
    })
    dab += (havana>kipa?'HAVANA WINS\n':'KIPA WINS\n') //최종 점수로 승리 판별
}

console.log(dab)