[백준 17165] Gosu

티어: 다5

 

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

 

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

문제

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

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

플레이어 x에서 플레이어 y로의 승리 경로를 K+1개의 정수 시퀀스 a_0 = x, a_1, ... 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), ... 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} = -
- 학생 i가 학생 j를 이겼다면 s_{i, j} = W
- 학생 j가 학생 i를 이겼다면 (즉, 학생 i가 학생 j에게 졌다면) s_{i, j} = L

출력

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

제한

- 2 ≤ N ≤ 3000
- s_{i, i} = - (1 ≤ i ≤ N)
- 만약 i ≠ j 라면 s_{i, j} = W or L (1 ≤ i ≤ N)
- 만약 s_{i, j} = W 라면 s_{j, i} = L (1 ≤ i, j ≤ N)
- 만약 s_{i, j} = L 라면 s_{j, i} = W (1 ≤ i, j ≤ N)

서브태스크 1 (40점)

N ≤ 100

서브태스크 2 (60점)
이 서브태스크는 추가 제약 조건이 없습니다.

 

 

해설

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

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

a로부터 b의 승리 경로를 a -> s -> ... -> b 라고 하자. b는 s에 속하는 모든 학생도 이겨야한다. 만약 그렇지 않다면 a -> s -> 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)
}