[백준 17165] Gosu

티어: 다5

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

지문이 영어로 되어 있어 한국어 번역을 첨부합니다.

문제#

호는 태보라는 무술의 전문가입니다. 그녀는 태보 학교를 운영하고 있으며, 학교에는 $N$명의 학생이 있습니다. 호는 태보를 가르치기에는 너무 나이가 들어서, 학교를 한 명의 학생에게 물려주려고 합니다. 적합한 후보를 찾기 위해 호는 모든 학생들 사이에서 총 $N(N - 1) / 2$번 태보 대결을 시켰습니다. 태보 대결에서는 정확히 한 명이 이기고, 한 명이 집니다. 호는 태보의 고수인 학생에게 학교를 물려주려고 합니다.

고수는 한국어로 게임, 스포츠, 프로그래밍 대회 등에서 매우 뛰어난 사람을 의미합니다. 태보에서 고수는 다른 의미를 가집니다.

플레이어 $x$에서 플레이어 $y$로의 승리 경로를 $K + 1$개의 정수 시퀀스 $a_0 = x, a_1, \ldots, a_K = y$로 정의합니다. 여기서 학생 $a_i$는 학생 $a_{i+1}$을 이겼습니다. $K$를 이 승리 경로의 길이라고 합니다. 예를 들어, 길이 1의 승리 경로가 존재한다면, $x$가 $y$를 이겼다는 것을 바로 알 수 있습니다. 길이 2의 승리 경로가 존재한다면, $x$가 직접 $y$를 이기지 않았더라도, $x$가 이긴 어떤 플레이어 $z$가 $y$를 이겼다는 것을 의미합니다.

$d(x, y)$는 $x$에서 $y$로의 최소 승리 경로의 길이로 정의됩니다. 만약 그러한 경로가 존재하지 않는다면, $d(x, y) = 9000$으로 정의합니다. 경로의 길이는 0일 수도 있으므로, $d(i, i)$는 항상 0입니다.

호는 자신의 학생이 모든 종류의 상대에게 강하기를 원하므로, 학생 $i$의 약점을 $d(i, 1), d(i, 2), \ldots, d(i, N)$ 중 최댓값으로 정의합니다. 학생 $i$가 태보의 고수가 되려면, 학생 $i$의 약점이 모든 학생들의 약점 값 중 최소가 되어야 합니다. 이 정의에 따라 여러 명의 고수가 존재할 수 있습니다.

호는 나이가 들어 누가 고수인지 알 수 없으므로, 여러분의 임무는 고수와 고수의 약점 값을 찾아 호를 도와주는 것입니다. 만약 여러 명의 고수가 존재한다면, 그중 아무거나 출력해도 됩니다.

입력#

첫 번째 줄에는 학생의 수 $N$이 주어집니다.

두 번째 줄부터 이어지는 $N$개의 줄 중에 $i$번째 줄에는 W, L, -로 구성된 문자열 $s_i$가 주어집니다. $s_i$의 $j$번째 문자를 $s_{i, j}$라고 할 때, $s_{i, j}$는 다음과 같이 주어집니다:

• $i = j$라면 $s_{i, j} = \text{-}$
• 학생 $i$가 학생 $j$를 이겼다면 $s_{i, j} = \text{W}$
• 학생 $j$가 학생 $i$를 이겼다면 (즉, 학생 $i$가 학생 $j$에게 졌다면) $s_{i, j} = \text{L}$

출력#

두 개의 정수 $d$와 $u$를 공백으로 구분하여 출력합니다. 여기서 학생 $u$는 고수이고, $d$는 학생 $u$의 약점 값입니다. 만약 여러 개의 정답이 있다면, 그중 아무거나 출력해도 됩니다.

제한#

• $2 \le N \le 3000$
• $s_{i, i} = \text{-}$ ($1 \le i \le N$)
• 만약 $i \ne j$라면 $s_{i, j} = \text{W}$ or $\text{L}$ ($1 \le i, j \le N$)
• 만약 $s_{i, j} = \text{W}$라면 $s_{j, i} = \text{L}$ ($1 \le i, j \le N$)
• 만약 $s_{i, j} = \text{L}$라면 $s_{j, i} = \text{W}$ ($1 \le i, j \le N$)

서브태스크 1 (40점)

$N \le 100$

서브태스크 2 (60점)

이 서브태스크는 추가 제약 조건이 없습니다.

해설#

가장 많은 승리를 거둔 학생 $a$가 가지는 약점 값을 $d(a, b) \ge 3$이라고 가정하면, $a \to b$인 경로가 존재해서는 안 된다.

따라서 $d(b, a) = 1$이고 $b$는 $a$를 이긴다.

$a$로부터 $b$의 승리 경로를 $a \to s \to \cdots \to b$라고 하자. $b$는 $s$에 속하는 모든 학생도 이겨야 한다. 만약 그렇지 않다면 $a \to s \to b$인 승리 경로가 만들어져 $d(a, b) = 2$가 되어 처음 가정에 모순이 생긴다. 따라서 $d(b, s) = 1$이다.

이제 $b$는 $a$가 이기는 모든 상대 $s$를 이기고, 추가로 $a$ 또한 이긴다. 따라서 $b$는 $a$보다 더 많은 승리를 거두게 된다. 이는 $a$가 가장 많은 승리를 거둔 학생이라는 처음 가정에 모순이다. 따라서 가장 많은 승리를 거둔 학생이 가지는 약점 값은 2 이하이다.

이제 경우를 나누어보자. 약점 값이 1이 되는 경우는 모든 학생을 상대로 전부 이기는 방법밖에 없다.

또한, 그렇지 않은 나머지 학생들의 약점 값은 항상 2일 것이다.

따라서 가장 많은 승리를 한 학생은 항상 고수이고, 이 학생이 모든 학생을 이겼다면 약점 값을 1, 그렇지 않다면 2를 선택하면 된다.

var input = require('fs').readFileSync(0).toString().trim().split('\n')
var N = +input[0]
var p = -1//승리 횟수
var q = 0//학생 번호
for(var i = 1; i <= N; i++) {
    if(p < input[i].split('W').length - 1) {
        p = input[i].split('W').length - 1
        q = i
    }
}
if(N - 1 == p) {//모든 학생을 이겼다면 승리 횟수는 N-1 이다.
    console.log('1 ' + q)
}else {
    console.log('2 ' + q)
}