TIL

알고리즘 문제를 풀다보면 여러 방향으로 이동해야하는 경우를 많이 마주한다.

ex) n 방향 탐색하는 문제라던지 ... https://www.acmicpc.net/problem/16926 이런문제라던지.. BFS라던지...DFS라던지...

그때 마다 int dx [], int dy[]를 써왔는데

이해는 제대로 하지 않고 답지를 보고 외우듯이 사용했었다...

오늘이 되어서야 dx[] dy []위치 값에 대해서 이해를 제대로 했다고 생각이 든다...ㅠㅠㅠㅠㅠ 왜냐면.. 백준 16926 이 문제 풀이를 보고 나서야.... 제대로 이해했기 때문이다...ㅠㅠㅠ

여기서 부터는 내가 이해한 내용을 바탕으로 서술

왜 dx, dy 라고 표현 하는가?

일단 2차원 배열을 쉽게 이해하기 위해서 우리는 x,y 축이라고 생각(나만 그러는 걸수도)

하기에 x축(코딩에선 arr) 이동을 해야한다. 할 때 보통 수학기호로 dx를 많이 사용하니 dx를 사용한다고 생각한다.

그치만 나의 경우 보통 선언을 할때 int arr [x'][y'] 이렇게 하는데..

수학에서의 x축이동은 코딩세계에선 y'를 이동하는 것이다. 그럼 수학에서의 y축 이동은 코딩세계에서 x'를 이동하는 것이다.

물론 다들 아는 사실을 왜 설명하냐면... 나의 경우는 int dx [] ={1,-1,0,0}, int dy [] ={0,0,1,-1} 이렇게만 항상 암기 식으로 생각했기 때문에....ㅠㅠㅠㅠㅠ 방향에 대한 이해도가 떨어졌었어서 다시한번 말하지만.. 백준 16926 이걸 보고 나서야 이해했기 때문이다.

dx dy는 항상 같이 다닌다고 생각해야한다.

이미지를 그리면 이렇게 된다...

솔직히 처음에 나도 이걸 봤을때 왜 이걸 이해 못 해.. 라는 말을 이어 나가려 했을때... 표에서 틀린점을 찾아서 2번이나 고친...멍청이다..ㅠㅠㅠㅠㅠ

위의 표는 8방향 이동을 표현한 내용이나, 여기저기에 응용될 수 있다.

백준 16926 여기서 사용된 것은 값의 이동이 어떻게 이루어지는 지 생각해봐야한다.

값이 반시계 방향 으로 이동한다고 했을때 이동방향은 우상좌하 이런 방식으로 이동한다고 볼 수있다.

반대로 값이 시계 방향으로 이동한다 했을때 이동방향은 하우상좌 이런 방식으로 이동한다고 볼 수 있다. (이건 값의 시작점이 어디냐에 따라서 달라질거 같다. 일단 나의 경우는 좌상(0,0)자리값이 이동하는 것을 기반으로 생각했다. )

이런식의 발상이 진행이 된다는 걸... 답지를 보고 깨달았다..ㅠㅠㅠㅠ

내 문제 풀이는

1. 4등분하기

처음에 생각한 아이디어론 4등분을 하는 거였으나... 이게 -> 노가다로 간다는 걸 깨닫고 접음...

2. x,y 축 값 합으로 생각하기

얘도 최외곽에서만 적용이 되고 바퀴 구분이 안된다는 사실을 깨달음..

3. 대각선들의 경우가 이상하다는 걸 발견(정사각형의 경우 직사각형은 아됨)

0,0 1,1 2,2 ..(i,i) 와 (0,n),(1,n-1)...(n,0)... 여기까지는 생각을 했는데 여기까지 오는데도 한 2시간 걸림...

솔직히 dx,dy를 생각 안한건 아닌데.. 아니겠지라고 생각함..

오늘의 결론... 모든걸 다 시도해보자.. 그리고 방향문제는 dx dy를 최우선으로 생각할 것...ㅠㅠ

그리고 내일 자고 일어나서 백준 문제 다시 풀어봐야지...