일요일 아침의 데이트 - BOJ 1445

일요일 아침의 데이트

BOJ 문제집에서 보게 된 문제.

1. Naive

가장 간단하게 접근하는 방법은 Brute Force한 풀이법이다.

시작점 F에서 모든 경로를 다 가보면서 S에 도달할 수 있는 모든 경우를 따진다.

물론, 이와같이 짜면 시간초과가 날 것이 분명하다.

2. O(N^2M^2(N+M)) DP - 1

가장 많이 쓰레기를 지나는 방법은 N+M-3개의 쓰레기를 지나는 방법이다. (시작점과 끝점이 대각선 끝에 위치하고 나머지 모든 지역이 쓰레기일 경우)

또한, 가장 많이 돌아서 쓰레기 옆을 지나는 방법은 NM보다는 작다.

이를 이용해 dp를 다음과 같이 세우자.

dp[x][y][a][b] = {  (x,y) 격자에 도달하는 경로 중, (쓰레기를 밟은 수, 쓰레기 옆을 지난 수) 가 (a,b) 인 경로가 존재하는가?   }

위 식에서 x,y는 최대 N,M 이고, a는 N+M, b는 NM 보다 작다.

dp에서 값을 참조하는 것은 위, 아래, 좌측, 우측 4가지에서 오는 경우만 고려하면 된다. 방향을 잡기 어려우므로 시작점에서부터 BFS를 하는 형태로 진행하면 된다.

따라서 시간복잡도는 O(N^2M^2(N+M)).

공간복잡도 또한 (N^2M^2(N+M)) 인데, 계산해보면 3억 조금 넘게 나온다. 하지만 위 dp에서 필요한 것은 가능 여부이므로, bool을 이용해 메모리를 줄이면 얼추 맞을 것 같다.

(bool이 실제 사용되는 것은 1Bit 인데.., 언젠가 1Byte라고 들은 적이 있어서)

3. O(N^2M^2(N+M)) DP - 2

위와 같은 dp에서 공간복잡도를 낮춰보자.

위 dp식에서 a와 b는 같은 x,y에 대해서 독립적이다. 이후 가는 경로들도 서로다른 a,b에 대해선 모두 독립적이란걸 알 수 있다.

즉, 어떠한 경로의 (a,b) 집합들에서 문제 상황에서의 더 좋은 경로가 발생한다면, 이외의 다른 경로들에서는 어떠한 경우도 더 좋은 경로가 발생할 수 없다.

이를 이용해 dp에서 갱신되는 때마다 다시 탐색을 해주는 방법을 시도할 수 있다. (Brute Force의 발전형태라 볼 수 있다.)

dp[x][y] = (x,y) 격자를 지나는 최소 (a,b)  (단, (a,b)의 비교연산은 문제 상황과 같다.)

위와 같이 dp를 세우고 나면 [a][b] 부분을 떼고서도 2번의 시간복잡도를 가질 수 있다. dp[x][y]가 갱신될 때마다 새로 탐색을 진행해주면 된다.

2번의 접근과 같이 실제 탐색이 이루어 지는 경우는 N^2M^2(N+M) 보다 클 수 없다.

따라서 시간복잡도 O(N^2M^2(N+M)), 공간복잡도 (NM)

4. O(N^2M^2)

특정한 격자에서의 (a,b)가 최소라고 가정하자.

이 때, 이 격자의 (a,b)가 가능하게 한 경로상에서 현 격자와 인접한 격자의 (a',b')도 그 격자에 대해서 최소이다.

특정 격자에서의 (a,b)가 최소라면, 그 격자의 (a,b)에서 다른 인접한 격자로 가는 경로는 현재의 격자를 통해 인접한 격자로 가는 경우의 최소 (a',b')을 가지게 된다. (바로 윗줄의 역은 아니다.)

윗 줄의 내용과 문제상황을 자세히 보면, 특정 순간까지에 대해 어떠한 격자들의 최소 (a,b)를 가지고 있으면, 그 격자집합 중에서 최소 (a,b)를 가진 격자로부터 이동하는 경로는 무조건 최소의 (a',b')을 가진다는 것을 알 수 있다.

이를 이용해 처음 격자 F에서는 최소임이 보장되므로, 배열에 F에 대한 (x,y)와 (a,b)에 대한 정보를 넣고, 현재까지 방문했으면서 아직 인접한 경로들로 이동하지 않은 격자들 중에 (a,b)를 최소로 하는 격자를 선택, 그 격자로부터 다시 인접한 격자들을 방문하는 형태로 진행한다. 앞에서 제시한 근거들로 인해 이러한 방법에서 새로 방문하게 되는 격자들이 가지는 (a',b')은 그 격자에서의 최소 (a',b')임이 보장된다.

각각의 격자 수 NM, 방문했으면서 인접한 경로로 이동하지 않은 격자가 NM개보다 적게 생기므로 이를 선형으로 탐색하여 O(N^2M^2)에 관리할 수 있다. 

5. O(NMlg(NM))

4번의 방법과 동일한 접근을 이용한다.

하지만, 방문했으면서 인접한 경로로 이동하지 않은 격자들의 (a,b)에 대한 우선순위가 문제에 제시되어 있으므로, 이를 heap을 이용하여 관리, O(NMlg(NM))에 해결할 수 있다.