leeingyun96   3년 전

일반적인 dfs, bfs로도 풀 수 있긴 합니다만 pypy로도 아슬아슬합니다. 그 이유는 경로의 반복에 있습니다.

row 3, col 3의 E를 보십시오. ㄱ과 같은 모양으로 접근해서 E를 왔다면 row 3, col 3, visited_alpha ABCDE일 겁니다. 그리고 dfs를 따라서 먼 길을 진행하겠지요. 문제는 ㄴ과 같은 모양으로 E를 왔더라도 여전히 row 3, col 3, visited_alpha ABCDE일 겁니다. 그리고 dfs를 따라서 먼 길을 가겠지요. 이미 지나간 길요. 이 과정에서 시간 낭비가 많이 됩니다.

따라서 row 좌표, col 좌표, alphabet 여부를 dp처럼 저장해야 합니다. 일반적인 그래프 문제에서는 visited_alpha이 아닌 visited_coordinates 여부로 중복을 확인하지만, 이 문제는 동일좌표&다른알파벳 역시 포함해야 하기 때문에 뭔가에 저장을 좌표, 알파벳 둘 다 해야 합니다.

제대로 된 설명을 저만 늦게 찾은 건진 모르겠는데 5시간 걸려서 찾은 거라 공유하고자 합니다.

https://leeingyun96.tistory.com/22

우왕 감사합니다

댓글을 작성하려면 로그인해야 합니다.