이 문제는 이곳에서 확인할 수 있습니다.

이 문제는 알파벳으로 구성된 2차원 배열에서 중복 없이 연결할 수 있는 최대 길이를 구하는 문제입니다.

2차원 배열을 순회하여 문제를 해결해야하므로 DFS 혹은 BFS로 문제를 해결할 수 있습니다.
하지만 배열에 장애물이 없고 알파벳 중복이 불가능하다는 제약밖에 없기 때문에 BFS로 문제를 해결하기에는 무리가 있습니다. 인접한 알파벳은 최소한으로 중복되지 않도록 배열된 경우 큐에 수 많은 데이터가 쌓이기 때문에 메모리 초과나 시간 초과가 발생할 수 있습니다.
그러므로 DFS와 백트랙킹을 통해 문제를 해결해야 합니다.


칸에 대한 방문 검사가 아닌 알파벳에 대한 방문 검사를 진행합니다.
칸을 방문한 것과 상관 없이 현재 알파벳이 중복되지 않은 알파벳이라면 방문을 합니다.
더 길게 돌아와서 해당 칸을 방문할 경우가 있기 때문입니다.

백트랙킹을 해줘야하기 때문에 DFS 이후 다시 방문 여부를 false로 바꾸어줍니다.


최초 시작점인 (0, 0) 의 알파벳에 대한 방문 여부를 true로 바꾸어주는 것을 잊지마세요!

profile
자바스크립트로 개발하는 새내기입니다.

0개의 댓글