백준 1913 달팽이 Kotlin (구현)

문제 출처 : https://www.acmicpc.net/problem/1913

1913번: 달팽이

문제

홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다.

9	2	3
8	1	4
7	6	5

25	10	11	12	13
24	9	2	3	14
23	8	1	4	15
22	7	6	5	16
21	20	19	18	17

N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.

입력

첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

출력

N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

알고리즘 분류

• 구현

풀이

규칙을 찾으면 쉽게 풀 수 있다.

다만, 구현 문제들은 이름값한다. 구현이 까다롭다.

그래도 이 문제는 그렇게 까다롭진 않은 편이다?

 

우선 시작 지점은 항상 [N/2][N/2]가 된다.

1부터 차례대로 쫓아가보자.

1에서 상 방향으로 이동 -> 2

2에서 우 방향으로 이동 -> 3

3에서 하 방향으로 이동 -> 4

4에서 하 방향으로 이동 -> 5

5에서 좌 방향으로 이동 -> 6

6에서 좌 방향으로 이동 -> 7

7에서 상 방향으로 이동 -> 8

8에서 상 방향으로 이동 -> 9

9에서 상 방향으로 이동 -> 10

10에서 우 방향으로 이동 -> 11

 

규칙이 보인다.

상 1

우 1

하 2

좌 2

상 3

우 3

하 4

좌 4

즉, 방향의 순서는 상,우,하,좌이며, 방향이 두 번 바뀔 때마다, 같은 방향으로 이동하는 최대 횟수가 1씩 증가한다.

따라서, 시작 지점 r,c를 구하고,

r,c에서부터 상우하좌 순으로, 현재 방향을 %4하여 다음 칸을 찾고, num을 넣어준다.

각 방향에서 최대 이동 횟수에 도달하면 방향을 바꿔주고, 방향이 2번째 바뀌었다면 최대 이동 횟수도 늘려준다.

아래의 코드를 보고 이해해 보자!

 

코드

//3<=n<=999
//안에서 바깥으로
//시작점 n/2 n/2
//상우하좌 순
val dir = arrayOf(arrayOf(-1,0),arrayOf(0,1),arrayOf(1,0),arrayOf(0,-1))

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val find = br.readLine().toInt()
    val graph= Array(n){IntArray(n)}
    var num = 1
    var curDir=0
    var moveMax=1
    var moveCnt=0
    var r=n/2
    var c=n/2
    var answer = Pair(r,c)
    graph[r][c]=num
    //방향 두 번 바뀔때마다 이동 칸 증가
    //11 22 33 44 55 66 7
    while(true){
        r += dir[curDir%4][0]
        c += dir[curDir%4][1]
        if(r !in 0 until n || c !in 0 until n)
            break

        graph[r][c]=++num
        moveCnt++
        if(moveCnt==moveMax){
            curDir++
            moveCnt=0
            if(curDir%2==0){
                moveMax++
            }
        }
        if(num==find){
            answer = Pair(r,c)
        }
    }

    for(i in graph.indices){
        for(j in graph[i].indices){
            write("${graph[i][j]} ")
        }
        write("\n")
    }
    write("${answer.first+1} ${answer.second+1}")
    
    close()
}