삼각 달팽이

링크: https://school.programmers.co.kr/learn/courses/30/lessons/68645
문제분류 : 배열
난이도 : Level 2
풀이시간 : 40분
결과: 실패

회고

풀이 아이디어는 그다지 어렵지 않았다.
문제를 처음 봤을 때, 풀이 방법이 바로 생각났고 시간 복잡도도 완전 탐색을 할 경우
1초 이내라는 것을 확인했기 때문에 바로 답이 나올거라 생각했다.
하지만 예제 케이스 3개(테스트1, 2, 3)를 제외한 나머지 케이스는 실패했다.
모범 답안은 2개가 있는데, 모범 답안1과 풀이 과정은 거의 똑같았다.
차이가 있다면 내 코드는 반복문에 for를 사용한 것이다.
모범 답안을 분석하면서 엣지케이스를 분별하는 능력과 실수하지 않는 코드를 만드는 걸 연습해야겠다.

내 코드

모범답안 1

내 풀이와 차이점은 삼각형을 채워넣는 방식에 있다.

'아래 -> 오른쪽 -> 왼쪽 위'로 이동하면서 값을 채우는 것은 동일하지만
이 코드는 이동하기 전에 이동해도 되는 위치인지 검사한다.
그리고 이동할 수 없는 위치인 경우 break로 루프를 멈춘다.
이미 값을 채운 위치는 이동하지 않고 방향을 바꿔 값을 채우지 않은 위치부터 다시 시작한다.

확실히 안전한 방식으로 값을 채워넣어 좋은 방법이라 생각된다.
하지만 내 코드와 어떤 부분에서 차이가 나는지 잘 모르겠다.
더 공부해봐야 할거 같다.

모범답안 2

모범답안 1보다 훨씬 간결하고 안전한 방법으로 작성되었다.
일단 규칙적으로 반복되는 부분들을 추상화 시킨게 가장 큰 차이점이다.
dx, dy 배열로 방향을 설정하는 건 내가 DFS나 BFS에서 자주 쓰던 방법인데,
이렇게 방향 전환을 할때 사용할 수 있다는 걸 잊고 있었다.

while문 안에서 이동할 위치를 미리 체크하고 만일 이동할 수 없으면
dir = (dir + 1) % 3으로 방향을 전환해준다.
여기서 modulo 연산을 해준 이유는 방향 전환이 반복되는 걸, 0 -> 1 -> 2로 표현해야하기 때문이다.
(modulo 연산은 나머지 정리에 의해 '나누는 값 - 1'로 나오기 때문에)

만일 방향을 전환한 후에도 이동하는 위치에 값을 채울 수 없다면, 반복문을 break로 종료한다.
왜냐하면, 방향을 전환한 후에 이동할 수 없는 위치이거나,
값이 이미 채워져있다면(0이 아니라면) 규칙대로 삼각형 배열을 모두 돈 것이기 때문이다.