최적화 - 3중 for문을 쓰지 않기 위해 나온 테크닉, flattening the state space

2025년 상반기 오전 2번 문제 개구리의 여행 문제를 풀다 보니 계속 시간초과가 나는 문제가 발생했다.

이러한 시간문제에 맞닥뜨리게 되니 자연스레 최적화에 관심이 갔다.

 

최적화의 방법 중 중첩 for문을 최대한 줄이는 방법이 하나 있더라.

 

원래

1. row

2. col

3. jumpPower

 

위 세 변수에 대해 각각 for문을 돌며 3차원 행렬을 관리해야 한다. 근데 Dijkstra 알고리즘의 경우 노드라는 하나의 값에 대한 최단 거리를 계산하다 보니 이러한 하나의 state 값으로 만들어 줄 수 있다고 한다.

 

그래서 다음과 같이 인덱스를 "펴는" 걸 생각하게 된다.

• 2D 배열을 1D로 변환할 때 row * width + col  같은 걸 사용한다.
• 거기에 추가적인 차원이 더 필요하다면 곱해주는 계수를 하나 더 추가한다.

그렇다면 2D 좌표를 1D로 바꿀 때 다른 행렬 인덱스인데 같은 값이 나오는 경우는 없는 것이 확실한가?

 

=> 절대! NEVER!!! 안 나온다.

이를 수식으로 증명하면 다음과 같다.

(row - 1) * gridSize + (col - 1)

(row - 1) * 한 줄에 들어가는 칸 수 + (col - 1) # 행 우선으로 번호를 매기는 방식

 

예시

gridSize = 4 # 예시

row=1, col=1 #→ (1-1)*4 + (1-1) = 0
row=1, col=2 #→ (1-1)*4 + (2-1) = 1
row=1, col=3 #→ (1-1)*4 + (3-1) = 2
row=1, col=4 #→ (1-1)*4 + (4-1) = 3

row=2, col=1 #→ (2-1)*4 + (1-1) = 4
row=2, col=2 #→ (2-1)*4 + (2-1) = 5
row=2, col=3 #→ (2-1)*4 + (3-1) = 6
row=2, col=4 #→ (2-1)*4 + (4-1) = 7


row r, col c → 인덱스 = (r-1) * gridSize + (c-1)

...

이렇게 절대 다른 (row, col) 쌍에서는 같은 값이 안나온다.

왜냐하면,

• row 가 바뀌면 (row - 1) * gridSize 항이 달라지므로 전체 값이 girdSize 단위로 차이가 생긴다.
• col 안에서는 row가 고정되어 있을 때 0 ~ (gridSize -1) 범위의 값만 추가가 된다. -> 고로 충돌 안한다.

수식으로 안정성 보장

• 총 인덱스 공간 : 0 ~ (gridSize * girdSize -1)
• 각 (row, col) 마다 유일한 번호를 가지게 된다.

 

세번째 차원이 포함 될때도 마찬가지

getStateId = MAX_JUMP_POWER * ((row - 1) * gridSize + (col - 1)) + (jumpPower - 1)

 

• (row, col) 쌍마다 MAX_JUMP_POWER 개의 jumpPower 상태를 안전하게 구분 할 수 있다
• 다른 (row, col) 쌍끼리는 MAX_JUMP_POWER 단위로 건너뛰기 때문에 절대 겹칩일이 없다.