[BOJ] 1952번 달팽이2

BOJ(백준) 1952번 달팽이2

문제 : M줄 N칸의 Matrix에 달팽이가 (0,0)부터 돌았을 때 몇 번 방향을 꺾는지 확인하는 문제다.

매우 쉬운 문제지만, 나의 코드의 1/3밖에 안되지만 속도도 더 빠른 BOJ id tncks0121님의 코드를 소개하고자 글을 쓴다.

 먼저 나의 코드는 아래와 같다.

fun main(args: Array<String>) {
    val (r,c)= readLine()!!.split(' ').map { it.toInt() }
    val map=Array(r){IntArray(c)}
    val dx= arrayOf(0,1,0,-1)
    val dy= arrayOf(1,0,-1,0)
    var res=0
    var count=1


    fun go(x:Int,y:Int,dir:Int){
        map[x][y]=count++
        val bx=x+dx[dir]
        val by=y+dy[dir]
        if(bx in 0 until r && by in 0 until c && map[bx][by]==0){
            go(bx, by, dir)
        }
        else{
            res++
            if(map[x+dx[(dir+1)%4]][y+dy[(dir+1)%4]]==0)
               go(x+dx[(dir+1)%4],y+dy[(dir+1)%4],(dir+1)%4)
        }
    }
    map[0][0]=1
    go(0,0,0)
    println(res-1)
}

 나의 코드 개념은 처음(0,0)부터 돌면서 matrix에 다 숫자를 써준다는 것이다. 

tncks님의 코드를 보고 감탄을 할 정도로 내 코드는 역겨웠다....

 다음은 tncks0121님의 코드이다.

fun main(args: Array<String>) {
  fun go(n: Int, m: Int): Int = when {
    n == 1 -> 0
    m == 1 -> 1
    n == 2 -> 2
    m == 2 -> 3
    else -> 4 + go(n - 2, m - 2) 
  }
  val (M, N) = readLine()!!.split(" ").map{ it.toInt() }
  println(go(M, N))
}

  go 함수를 파헤쳐보자...

 go함수 내부의 when절 내부에 else문을 보면 4 + go(n-2, m-2) 로 되어있는데

이것은 한바퀴 돌았다는 것을 의미한다.  4 = 방향을 4번 바꿨다 = 한바퀴 돌았다. 

그리고 n과 m을 2씩 줄여서 재귀함수를 돌린다. 왜냐하면 한바퀴 돌면  Matrix의 행과 열의 양끝을 돈 것이므로...

이제 else위의 경우를 하나하나씩 살펴보자.

 n == 1 -> 0   : 이것은 row(행)가 1개밖에 없는 것으로  col(열)이 몇개가 되든 우측 방향으로 가기만 하면 끝난다는 생각이므로 , 0을 return하게 하였다.

 m == 1 -> 1    : 이것은 col이 1개밖에 없는 것으로 1을 return한다. 이유는 재귀를 돌고나면 우측방향으로 돌고있다고 생각하기 때문에(처음에 시작이 오른쪽 방향임), 그런데 현재 col이 1이므로 아래 방향으로 가야한다 = 한번 방향 전환을 해야함. 따라서 1을 return 한다.

 n == 2 -> 2   : 이 것은 row가 2인 상황이다. 위에 내용을 이해 했다면 왜 2를 return 하는지 알 수 있다.

한번 더 설명하자면, row가 2인 경우 col의 크기에 상관없이 방향 전환을  ( 우측 상단 끝, 우측 하단 끝) 이렇게 2번 하면 된다. 따라서 2를 return 한다.

 m == 2 -> 3 : 이 설명은 생략한다.

 

 결론 : 내 코드는 Matrix의 모든 Point를 다 돌아보도록 짰는데, 이 코드는 재귀를 몇번 돌지도 않는다.....

 

 일단 내가 판단하기에 잘 짰다고 생각해서 코드를 보고 퍼왔다. tncks님이 이 글을 보신다면 댓글좀요.

코틀린 좀 가르쳐줘요.