BOJ(백준) 1952번 달팽이2
문제 : M줄 N칸의 Matrix에 달팽이가 (0,0)부터 돌았을 때 몇 번 방향을 꺾는지 확인하는 문제다.
매우 쉬운 문제지만, 나의 코드의 1/3밖에 안되지만 속도도 더 빠른 BOJ id tncks0121님의 코드를 소개하고자 글을 쓴다.
먼저 나의 코드는 아래와 같다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | 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) } | cs |
나의 코드 개념은 처음(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)) } | cs |
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님이 이 글을 보신다면 댓글좀요.
코틀린 좀 가르쳐줘요.