[백준] 1987번 알파벳 - python

문제 출처

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

 

문제 풀이 및 코드

해당 문제는 dfs, bfs 문제로 경로마다 알파벳 종류를 파악해야 하는 문제였다. 필자는 bit연산을 이용해 알파벳을 저장했다. 알파벳이 26종류이니 a = 1, b= 2, c= 4이런식으로 사용했다. 따라서 dfs를 통해 경로가 진행될 때마다 해당 좌표의 알파벳을 지나왔는 지 체크하도록 visited라는 변수를 만들었다. 즉 visited에는 해당 경로를 지나며 거쳐온 알파벳들이 저장되어 있다.

 

정답은 맞췄지만, 3000ms가 넘는 시간이 걸려 다시 풀어 보았다. 말은 다시 풀었다고 했지만 그냥 백트래킹을 추가했다. (항상 한번 풀고 나서 시간초과로 백트래킹을 추가하는 것 같다...) Check라는 어레이를 만들어 특정 좌표를 지날 때 visited 정보를 비교했고, 이전에 해당 visited로 접근한 경우가 없을 때만 계속해서 탐색하도록 작성했다.

 

 

필자는 좌표에 도착했을 때 visited가 이전에 없었으면 저장하도록했다. 하지만 다른 고수님들의 코드를 보니 visited들을 모두 저장하지 않고 바로 이전의 visited만 저장하도록 했다. 다시 말해, 필자는 방문할 때마다 새로운 visited를 array에 추가하는 방향으로 저장했지만, 고수님들은 현재 visited만을 저장했다. dfs로 경로를 찾을 때 바로 이전의 경로와 크게 달라지지 않는 점을 활용한 것이다. 이전의 정보들을 검색하는데 오랜 시간이 걸리기 때문에 ,완벽한 백트래킹이 일어나지 않아도 효율적으로 진행하도록 바로 이전의 visited만 비교하도록 코드를 구현하셨다. 이를 이용해 코드를 수정했고 매우 빠른 시간에 코드가 실행되었다.