BOJ 1981 배열에서 이동

0이상 200이하의 숫자로 이루어져 있는 n*n짜리 배열이 주어지는데,  (1, 1) (맨 왼쪽 위)에서 (n, n) (맨 오른쪽 아래)로 이동하는 경로에 있는 숫자중에서 최대값과 최소값의 차이가 최소가 되도록 하는 문제이다. 각 경로의 최대값과 최소값의 차이 중 최소를 구하면 된다.

상, 하, 좌, 우로만 이동할 수 있다.
그리고 생각해보면 한 번 방문했던 곳을 또 방문하는 것은 무의미하다.

bfs로 해볼까 생각을 했지만... 그러면 모든 칸을 다 방문하기는 하지만 최대값과 최소값이 최소가 되는 경로를 방문하지는 못할 수 있다. 혹은 체크를 하지 않고(한 번 방문했던 곳도 또 방문하면서) 하면서 각 칸을 최소값으로 갱신해주면...음 그러면 너무 오래 걸리거나 메모리 초과가 날 것 같다.

dp로 접근해보려 한다.
d[r][c] = (1, 1)에서 (r, c)까지의 최대값과 최소값의 차이들 중 최소값...으로 하면 음...

문제 분류를 봤다.
bfs, 이분 탐색이라고 되어있다... 그래도 감이 안와서 질문게시판을 좀 참조했다.

아... 배열에 주어지는 숫자는 0이상 200이하이다. 즉 최대값과 최소값의 차이도 최소 0에서 최대 200까지이다. 구하는 값을 이분 탐색으로 정한 후, bfs를 통해 (1,1)에서 출발해서 (n, n)까지 도달할 수 있는지 탐색해보면 되는 것이다.

음 근데 질문게시판의 질문글, 답변글이 없었으면 나는 생각하지 못했을 거다... 음 정말 내 능력이 부족하다는 것을 다시금 느끼면서도 참 이렇게 풀 수 있다는 것을 알고나니 멋있고 재미있는 문제같다.

일단 구현해 봐야겠다.
막상 구현하려니 거대한 벽이 존재하는 느낌이다. 그냥 bfs를 해서는 안된다. check배열을 쓰지 않고 방문했던 곳을 또 방문한다면 무한 루프에 빠질 수 있다. 그렇지만 check배열을 써서 방문한 곳은 방문하지 않는다면, 정답인 경로를 찾지 못할 수 있다....
그래서 고민하다가 생각한 것이 check배열에 인자를 더 넣는 것이다.
바로 check[r][c][(1, 1)에서 (r,c)까지의 최소값][(1, 1)에서 (r,c)까지의 최대값] ... 이것이다. 처음에는 check[r][c][(1,1)에서 (r,c)까지의 최대값과 최소값의 차이]로 하려고 했지만, 최소값과, 최대값이 다르더라도 최대값과 최소값의 차이는 같을 수 있고, 그 경우 다음에 어떤 정점을 방문하느냐에 따라 결과가 달라질 수 있기 때문에 안된다.

하지만 그 경로까지의 최소값, 최대값이 같다면 뒤에 어떤 경로를 방문하든 당연히 똑같은 값이 나올 것이므로 이미 같은 최소값, 최대값으로 방문했었다면 또 방문할 필요가 없는 것이다. 근데 이렇게 해도 시간은 꽤 걸릴 것 같아 보인다.

그래서 한가지 더, 일단 답을 정하고 탐색하기 때문에, 최대값과 최소값의 차이가 그 답을 넘어가면 더이상 그 경로로는 탐색하지 않으면 bfs탐색을 더 줄여줄 수 있을 것이다.

다시 구현해 봐야겠다. 음 정말 만만치 않은 아름다운 문제같다.
음... 근데, 저 check배열을 선언하려고 하면 check[100][100][200][200]... 메모리 초과가 날 것이다. 음.... 좀 더 고민해 봐야한다.

결국... 어떤 분이 써놓으신 풀이와 코드를 보고 이해했다.
음 이분 탐색으로 답을 정하고 bfs로 그 답을 만족하면서 갈 수 있는지 탐색하는 것이 맞는데, 문제는 그 답을 만족하면서 갈 수 있는지 탐색하는 부분이었다. 한 번 방문한 곳을 또 방문하지 않게되면, 답을 만족하는 경로를 찾지 못할 수 있고, 최대값과 최소값의 차이로만 구별을 하게 되면 최소값과 최대값의 차이는 같아도 최소값, 최대값이 다른 경우에는 다음에 어떤 정점을 방문하냐에 따라 결과가 달라질 수 있기 때문에 결국은 최소값, 최대값을 다 체크하면서 bfs를 해야했다. 하지만 그러면 메모리 초과... 여기에서 막혔었는데, 풀이를 보고 정말 감탄했다.

이분 탐색으로 최소값과 최대값의 차이값 diff를 정하고... 그 diff를 최대값과 최소값의 차이로 가지는 경로에서의 최소값(혹은 최대값도 가능)이 뭔지도 정해놓고 탐색하는 것이다!
diff도 정해져있고, 최소값도 정해진다면 방문할 수 있는 칸이 제한이 될 것이다. 그래서 조금 전처리를 하고 bfs를 돌리든지 아니면 bfs를 돌리면서 최소값이상이고 최소값+diff이하인 칸 만 방문하게 bfs를 돌려서 (1,1)에서 (n, n)으로 갈 수 있는지 보면된다.
최소값은 최소0부터 200인데, 일단은 그 배열에서 최소값a와 최대값b를 구해서 a부터 시작해서 최대 b까지(좀 더 정확히는 b-diff까지) 해보면된다.

그러면 시간 복잡도는 이분탐색 log(2N) * (a~b까지 최소값 설정) 2*N * bfs N^2
대충 N^3 * log N 이 될 것 같다.
실제로 계산하면 대략 최대 log(200) * 200 * (10000+40000) = 대략 8천만?
10000+40000은 bfs시간 복잡도인 (V+E)를 나타낸 것인데, 정점은 10000개, 간선의 개수는 40000보다 적겠지만 계산 편의상 한 정점당 간선 4개라고 하고 40000으로 계산했다...
시간제한이 2초라 충분히 들어올 것이다.

일단 AC를 받았는데, 최소값을 정할 때, 내가 위에다가 좀 더 정확히는 b-diff까지 라고 적었는데, 이러면 틀릴 수 있다. diff값이 너무 커서 b-diff가 a값보다 클 경우, for문에서 조건을 체크할 때, 아예 최소값을 정하지 못하고 for문이 실행되지 않아버린다. 그러면 이분 탐색을 할 때, diff를 최대 b-a까지만 정하도록 하면 될 것 같다. left=0, right=b-a로 놓고 해보면 될 것 같다. AC를 받았다. 그리고 다른 분들의 코드를 보니 dfs를 쓴 코드도 꽤 보인다.
이 방식대로 하면 bfs대신 dfs를 써도 될 것 이다. 한 번 해봐야겠다.

dfs로 구현하다보니 떠올랐는데, 아까 bfs로 구현할 때, (1, 1)시작부분은 체크를 안해서 또 방문하는 일이 생길 것 같아 보인다. 한 번 체크하고 다시 제출해 봐야겠다. 음 똑같다...다시 생각해보니 또 방문해서 그 때 체크하는 것도 시간상으로는 별 차이 없을 것 같다.
그럼 계속해서 dfs로 수정해 봐야겠다. dfs로 구현할 때는 조금 까다로운 것이, 방문한 경로 중에 하나라도 diff이하를 만족시키면 true를 반환하게 하는 것이 살짝 까다로웠다.
그냥 간단하게 if(dfs(r, c)) return true 이런식으로 하나라도 true이면 true를 return하고, 모두 true가 아닌 경우에 false를 return하는 식으로 구현해야 한다.

dfs로 하니까 메모리와 시간이 아주 조금씩이나마 줄었다.
 참 좋은 문제였고, 내가 내 혼자 힘으로 푼 것이 아닌만큼 다음에 꼭 복습하고 다시 풀어봐야겠다.


참조 및 출처 : KSJ14님의 블로그