BBF.scala

package com.jayden.round20161A

import scala.collection.immutable.IndexedSeq

/**
  * Created by jaydenuk on 2016. 8. 12..
  */
object BBF extends App{

  def solve(list: List[Int]):Int = {

    def findCircleCountAndCouples(target: Int, 
                                  visited: List[Int], 
                                  graphed: List[Int], 
                                  couples: List[(Int, Int)],
                                  maxCircleSize: Int): (Int, List[(Int, Int)]) = {

      def findNewTarget(maxCircleSize:Int, nextCouples:List[(Int, Int)]): (Int, List[(Int, Int)]) = {
        val unvisited: IndexedSeq[Int] = list.indices diff (visited ++ graphed)
        if (unvisited.isEmpty) {
          (maxCircleSize, nextCouples)
        } else {
          findCircleCountAndCouples(unvisited.head, List(unvisited.head), visited ++ graphed, nextCouples, maxCircleSize)
        }
      }

      val friend = list(target)
      if (graphed.contains(friend)) {
        findNewTarget(maxCircleSize, couples)
      } else if (visited.contains(friend)) {
        val circleSize = visited.indexOf(friend) + 1
        val nextCouples = if (2 == circleSize) (friend, target) :: couples else couples

        findNewTarget(circleSize max maxCircleSize, nextCouples)
      } else {
        findCircleCountAndCouples(friend, friend +: visited, graphed, couples, maxCircleSize)
      }
    }

    val relations = list.zipWithIndex.groupBy(_._1).mapValues( x => x.map{case (key:Int, value:Int) => value})

    def findDeepest(queue:List[(Int, Int)], maxDepth:Int):Int = { //(id, 깊이)
      queue match {
        case Nil => maxDepth
        case (target, depth) :: xs =>
          findDeepest(queue.tail ++ relations.getOrElse(target, Nil).map(x => (x, depth + 1)), depth)
      }
    }

    def findDepth(one: Int, another: Int) = findDeepest(relations(one).filter(_ != another).map(x => (x, 2)), 1)
    def findCoupleDepth(left: Int, right: Int) = findDepth(left, right) + findDepth(right, left)

    val target = list.head
    val (circleCount, couples) = findCircleCountAndCouples(target, List(target), Nil, Nil, 0)

    if(couples.isEmpty){
      circleCount
    }else{
      couples.map { case (left, right) => {
        findCoupleDepth(left, right)
      }}.sum max circleCount
    }
  }



  def process(lineIn: Iterator[String])(lineOut: String => Unit) = {

    val count: Int = lineIn.next().toInt

    for(i <- 1 to count){

      lineIn.next()

      val bbfList = lineIn.next()
      val result = solve(bbfList.split(" ").map(_.toInt - 1).toList)
      lineOut(s"Case #$i: $result")
    }
  }

  val filename = "C-large-practice"
  val writer = new java.io.PrintWriter(filename + ".out")

  try {
    process(io.Source.fromFile(filename + ".in").getLines) { s =>
      writer.println(s); writer.flush()
    }
  } finally {
    writer.flush(); writer.close()
  }


}