카탄의 최장 도로
시간 제한4초메모리 제한512 MB
카탄 보드에서 세 플레이어가 각자 소유한 도로 구간만 한 번씩 지나며 만들 수 있는 가장 긴 길의 길이를 구합니다.
문제
카탄(Settlers of Catan)은 여러 플레이어가 육각형 격자 위에 건물을 지어 점수를 얻는 게임이다. 당신은 두 친구와 함께 그림 C.1의 보드에서 게임을 하고 있다. 보드는 정육각형 7개로 이루어져 있으며, 24개의 교차점(육각형의 꼭짓점)과 이들을 잇는 30개의 차선(육각형의 변)이 있다.
그림 C.1: 게임 보드.
게임에서 각 플레이어는 차선 위에 도로 조각을 지을 수 있다. 각 도로 조각은 정확히 한 플레이어가 소유한다. 차선 하나에는 도로 조각을 최대 하나만 지을 수 있다. 플레이어가 길이 인 도로를 가졌다는 것은, 서로 같을 수도 있는 교차점 개 가 있어서, 각 에 대해 와 을 잇는 서로 다른 도로 조각 개를 플레이어가 소유한다는 뜻이다.
가장 긴 도로를 가진 플레이어에게는 보상이 주어진다. 각 플레이어의 최장 도로 길이는 얼마인가?
입력
입력은 게임 보드를 텍스트로 나타낸 것이다. 보드는 19줄이며 크기는 19 × 31이다. 각 교차점은 '>' 또는 '<' 중 하나로 표현된다. 도로 조각이 없는 차선의 문자는 모두 '-', '/', '' 중 하나이다. 도로 조각이 있는 차선의 문자는 모두 '1', '2', '3' 중 하나이며, 그 차선의 도로 조각을 소유한 플레이어를 나타낸다. 입력의 나머지 문자는 모두 '.'이다.
도로 조각이 없는 빈 보드는 첫 번째 샘플 입력에 나와 있다. 빈 보드와 입력의 차이는 차선 전체가 '1', '2', '3' 중 하나로 바뀐 것뿐이라고 보장된다.
출력
플레이어 1, 플레이어 2, 플레이어 3 순서로 각 플레이어가 소유한 최장 도로의 길이를 출력한다.