[코드그라운드] 미궁 속의 방

출처 : 코드그라운드

정답 : 링크

이 문제의 경우 지그재그 매트릭스를 만드는 것이다. 과거에도 몇번 풀어봤던 유형인데 그때마다 햇갈려한다. 

이런문제는 당연히 배열을 만들어서 값을 채워넣고 출력하라는 말은 절대 아니다. 수식을 만들어서 계산하라는 의미이다.

먼저 수식을 만드는 방법은 참 많이 있을것이고 나보다 더 훌륭한 방법이 분명 있을것이지만 난 나의 방식대로 하였다.

접근 방법

1. 우선적으로 지그재그 이동방향은 좌표값으로 알 수 있다. 왼쪽 상단을 (1, 1)이라고 할 때, x+y-1을 하여 2로 나눈값이 홀수이냐 짝수이냐에 따라 왼쪽에서 오른쪽으로 커져가는지 오른쪽에서 왼쪽으로 커져가는지 알 수 있다.

2. 모든 좌표를 그대로 이동하였을때 왼쪽끝으로 오면 어떤수인지 알아내고자 한다. 그 후에 해당 좌표만큼 더해주거나 빼주면 끝인 것이다. 이때 배열을 반으로 나눠야 한다. 

   그 이유는 반으로 커져갈때는 일정한 규칙성을 가지지만 반이 끝났을때는 계속 줄어들게 되므로 규칙성이 깨지게 된다. 그러므로 반으로 나눠서 계산한다.

3. 수식을 찾는다. 수식은 개인적으로 경험을 토대로 유추해봤다.

val = 1 + (temp - 1) / 2 + odd[((temp - 1) - (temp - 1) / 2) - 1];

위와 같은 규칙을 가지게 되는데 temp는 x+y-1로 정의를 하고 있다. 이 규칙을 도입하면 왼쪽 에 어떤수가 위치하는지 알 수 있다. odd배열은 상단에 만들어 놨는데, 규칙에 따라서 수가 증가됨을 알기에 미리 만들어놓는다. 물론 이 수식마저 배열로써 규정시킬 수 있다.

4. 값이 왼쪽으로 뻣어나갈때 왼쪽끝이 아니라 하단에 위치하게 된다면 새로운 수식을 도입해야 한다. 필자는 수식을 만들다가 굳이 그럴 필요가 없지 않을까? 시간상으로 충분할 것 같은 생각이 들어 한번에 배열로써 만들고 계산하고자 하였다. 코드상의 22번째 라인부터 44번째 라인이 그 부분이다. 미리 배열로써 증가하는 규칙에 맞춰 배열을 한번에 만들어놓았다.

5. 다 구해졌으니 이제 왼쪽으로 뻣어나간 값에서 해당 좌표값을 빼거나 더해서 값을 구하고 더한다. 

이런 문제는 수식을 찾으라는 문제인데, 수식은 솔직히 그날의 컨디션이 중요한거같다. 

잘풀릴때는 한번에 찾아지지만 못찾을때는 정말 안찾아진다. 이 문제는 비교적 빠르게 찾은것 같다.