전형적인 DFS / BFS 문제였다.
1) 문제 풀이 아이디어를 잘못 생각했다.
BFS로 풀이한다면 단어를 변환하는 과정에서 앞서 이미 등장했던 단어는 다시 큐에 넣을 필요가 없다. 즉 방문처리가 필요하다. 왜냐하면 이미 재귀를 태웠다면 그 후에 동일한 단어가 나왔을 때 이 경우는 이전 경우보다 DEPTH가 같거나 더 깊기 때문에 최소 단계를 구하는 문제에서 필요 없는 연산과정이다.
여기서 한 번 잘못 생각해서 VISITED를 없애야 한다고 생각했다가 시간을 잡아먹었다. VISITED를 하면 안 된다고 생각했다. 만약 나중에 동일한 단어가 다시 등장했을 때, 이전 단계에서 등장한 경우는 TARGET에 도달하는 데 실패하지만, 나중에 등장했을 때는 성공하는 경우라면? 이러한 경우가 있으면 VISITED 처리해버렸을 때 정답 도출이 불가능하지 않을까?
이러한 경우는 없다. 어떤 단어가 어떤 DEPTH에서 등장하든지 그 단어가 TARGET에 도달할 수 있는지 여부는 동일하다. WORDS 배열에 있는 단어만을 사용하여, 알파벳 하나씩만을 변환해가며 TARGET에 도달해야 한다는 조건 외에 DEPTH가 달라질 때 변하는 조건이 없기 때문이다. VISITED 처리를 통해 나중에 등장한 단어는 VISITED 처리 된 단어를 사용할 수 없지만 이는 최소 단계를 정답으로 RETURN 하기 때문에 애초에 필요가 없다.
2) 시간복잡도 계산
처음에 최악의 경우 뽑은 단어의 10개 자리에 대하여 다른 50개 단어와 각 자리를 비교하는 500번의 연산이 TARGET에 도달할 때까지 발생하여 500^50(가장 늦게 찾을 경우) 라고 생각해서
무조건 시간 초과가 날 것이라 생각했는데 아이디어를 잘못 생각한 것이었다. 좀 더 세밀하게 어떤 연산이 발생하는지 주어진 문제의 값들과 함께 생각해야 한다. 처음에 각 자리를 다른 단어들과 비교하는 연산이 500번 일어나지만 이후 다음 단계에 등장한 단어들은 방문처리가 되므로써 다음 연산에서 빠지게 된다. 만약 각 단계에서 방문처리가 되는 단어가 1개 뿐이라고 해도 총 50번이면 모든 단어를 살펴보고 답이 도출되기 때문에 최악의 경우 500 * 50번 연산이 발생한다. 세밀하게 연산을 따지지 않은 점, 문제 아이디어를 잘못 생각한 점 때문에 계산 실수가 있었다.
3) 실수
문자열의 값 비교는 equals 메소드를 사용해야 하는데 비교 연산인 == 을 사용하는 실수를 했고, 디버깅 과정에서 찾았다.
