역으로 생각하는 문자열 변환과 DAG 위의 DFS + DP

A와 B 성공

이 문제를 제대로 해결하지 못했던 이유는 작업시간에 대한 계산을 제대로 하지 못했기 때문입니다. 이 문제의 조건에서는 A를 조작하여 B를 만들어라 라고 명시적으로 적혀있지만 이 방법 그대로 수행해서는 메모리 제한과 작업 시간 초과로 인해서 문제를 해결하지 못합니다. 이 문제에서 이야기 하는 조작 방법은 아래와 같습니다.

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.

이 문제는 오히려 B를 조작하여 A를 만들어야 하는 문제였습니다. 물론 이 방법도 생각을 했지만 작업 시간 계산을 전혀 잘못했습니다. 첫 번째 방법의 경우는 모든 경우의 수를 탐색해야 하는 게 맞았습니다. 이를 달성하기 위해서는 모든 경우의 수마다 2번의 작업이 추가되는 작업 시간이 O(2^N) 이기 때문에 주어진 문제의 제한 조건 내에 해결하지 못한다고 판단했습니다.

하지만 저는 이 반대의 경우 또한 마찬가지라고 생각했습니다. 하지만 실제로는 반대로 이 작업을 수행할 경우 문자열의 마지막 문자가 무엇인지에 따라 조건이 제한된다는 것을 알아채지 못했습니다.

이 문제의 조작 방법의 경우 문자열을 추가할 수 있는 경우는 "A" 혹은 "B" 이기 때문에 "A" 일 경우에는 문자열을 제거하고 "B"의 경우 문자열을 제거하고 문자열을 뒤집는 작업을 수행하면 B를 조작하여 A를 만들 수 있는가? 에 대한 정답을 O(N) 으로 해결할 수 있는 문제였습니다.

욕심쟁이 판다 성공

이 문제를 해결할 때 가장 헷갈린 부분은 DFS인지 다익스트라 알고리즘을 사용해야 하는지에 대해서 제대로 판단하지 못했다는 것입니다. 이 부분을 제대로 인지할 수 있어야 할 것 같다고 느꼈습니다.

이 문제에서 DFS를 사용해야 한다는 힌트는 이 그래프가 DAG 사이클이 없는 방향 그래프라는 특징을 갖는다는 것입니다. 이 문제의 조건은 다음 이동은 현재 먹은 값보다 큰 값으로 이동한다. 라는 제약조건이 있기 때문에 방향을 가지면서 순환될 수 없는 구조를 갖고 있습니다.

그리고 이러한 특징에서 추가적으로 알 수 있는 것은 이 문제는 최장 거리로 이동해야 한다는 것이었습니다. 그래프 관련 문제에서 최단/최장 거리를 요구하는 문제의 경우 DFS + DP로 해결해야 하는 문제라는 것을 반드시 주의해야 할 것 같습니다.

또한 BFS, DFS의 차이점 또한 알고 있어야 합니다. DFS/재귀 방식의 경우 Lazy Evaluation 값을 누적하여 나중에 계산하는 방식이고 BFS의 경우 Eager Evaluation 방식으로 현재 값을 퍼트려 나가는 방식으로 계산한다는 것을 명심해야 합니다.

DFS의 계산 방식

(1) 파라미터 전달 방식 (혼동하기 쉬운 접근)

// 보통의 탐색(방문 여부 확인 등)에서 많이 쓰는 방식
function dfs(x, y, count) {
  // 다음 칸으로 갈 때 count + 1을 해서 넘겨줌
  dfs(nx, ny, count + 1);
}

(2) 반환 값 누적 방식 (이 문제의 정답 접근)

costs[cx][cy] = Math.max(dfs(nx, ny) + 1, costs[cx][cy]);