Python 백준 1987번 - 알파벳 (시간 초과 해결)

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

 

생각

우선 탐색을 하는데 (1,1)이라는 root 부터 시작을 하기 때문에, Bfs로 탐색하면서 해당 지점을 방문했다는 표시를 남기고, 상하좌우 4방향에 탐색을 진행할때 그곳이 이전에 방문을 했거나, 범위에서 벗어난 경우 Return을 시켜서 백트래킹이용하고 모든 경우를 구하려고 했다.

또한 문제의 함정이 하나 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다 이 말이 핵심이다. 그러니 다시 뒤로 돌아간다면 현재 방문한 것은 제외시켜야 한다.

 

코드

 

오답 이유에 대해서

우선 bfs를 사용하는데, queue 자료구조를 안 쓰게 되면서 재귀 적으로 구현한 점이 문제일 수 있을 것이다. 또한 visited라는 list에 계속 remove를 하는데 이 탐색 시간에서도 문제였을 것이다. 그래서 queue를 사용하고 백트레킹을 적용할때 예외에 대한 시간을 줄여보려고 한다.

 

코드2

 

알게된 점 

백트래킹을 적용할때 Set 자료구조를 사용하여 queue를 구현한다면, 더 효율적으로 탐색할 수 있다는 것