kotlin 프로그래머스 lv2 삼각 달팽이

해당 문제를 읽고나서 배열의 크기와 삼각형이 채워지는 방향에대해 생각하게 되었다.

배열의 크기는 수열의 합공식으로 적용되어 코드를 아래와 같이 작성했다.

val answer = IntArray((n*(n+1))/2)

반시계방향이므로 숫자가 채워지는 방향이 y는 아래로 커지는 방향으로 x는 오른쪽으로 커지는방향으로 마지막으로 좌상단으로 이동할때는 x와 y가 작아지는 방향으로 이동한다.

그래서 코드를 아래와 같이 작성했다.

val directions = arrayOf(intArrayOf(1,0),intArrayOf(0,1),intArrayOf(-1,-1))  //[[1,0],[0,1],[-1,-1]]

해당 코드는 삼각형을 채우기 위한 방향을 나타내고, 아래방향으로 y좌표가 증가하고 [0,1] 로 작성했다.

우측방향으로 x좌효가 증가하고 [1,0]로 작성했다.

좌상단 방향으로 x,y 둘다 감소하고, [-1,-1]로 작성했다.

var num = 1 //현재 채워진 값

var row = 0 //현재 행

var col = 0 //현재 열

var directionIdx = 0 //방향 인덱스

그 후 dfs방식을 통해 삼각형을 채워나갔다.

 

※dfs 알고리즘 DFS(깊이 우선 탐색) 알고리즘은 그래프나 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나이다. 이 알고리즘은 특정한 경로를 따라 최대한 깊이까지 탐색한 후, 더 이상 탐색할 수 없을 때 다시 돌아와 다른 경로로 탐색을 진행한다.

먼저 현재 채울 숫자(num)가 삼각형의 총 요소 수보다 작거나 같을 때까지 다음을 반복한다.

-현재 위치에 현재 숫자를 결과 배열에 채운다.

-현재 위치와 방향을 기반으로 다음 위치를 계산한다.

-다음 위치가 삼각형의 범위 내에 있고, 셀이 비어있으면 다음 위치로 이동한다.

그렇지 않으면 방향을 변경하고 이동한다.

-다음 반복을 위해 현재 숫자(num)을 업데이트한다.

코드는 아래와 같이 작성했다.

결과는 예상대로 잘 나왔다.

dfs문제를 많이 풀어봐야될것 같다.