[BOJ/백준] 1987. 알파벳 (python)

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

Problem

각 칸에 알파벳이 적혀있는데 방문한 칸의 알파벳이 중복되지 않게 상하좌우로 움직여 최대 몇 칸을 갈 수 있는지 구하는 문제
​

Solution

처음에는 dfs와 backtracking을 이용해 풀었는데 잘못된 부분이 있었는지 계속해서 시간초과가 났다.

그래서 bfs로 해결 방법을 바꾸었는데 그마저도 시간 초과가 났다.

알고보니 리스트를 이용해 if value in list 처럼 in 연산을 하면 리스트의 처음부터 끝까지 다 돌아야 하므로 O(n) 시간이 소요된다.

이 문제는 방문한 알파벳의 순서는 전혀 중요하지 않으므로 set 을 사용해주면 시간을 줄일 수 있다.
​

1. 갈 수 있는 최대 거리를 저장해줄 변수 maxV, set 타입의 변수 queue를 생성해주고

   set 에는 시작 점을 저장해준다.

2. queue에 값이 있으면 계속 반복

3. queue에서 pop 한 값들을 각각 x, y, visited에 넣어주고 반복문의 시작점에서 기존의 maxV와 지금껏 지나온 알파벳의 갯수 중 큰 값으로 maxV를 갱신해준다.

4. 만약 maxV가 26이면 모든 알파벳을 다 거쳐온 것이므로 더 이상 들어갈 수 있는 알파벳이 없기 때문에 종료한다.

5. 상하좌우를 탐색하기 위해 반복문 4번 수행

6. 다음 칸이 board 크기 내에 있고, 해당 알파벳이 방문한 적이 없으면 queue에 add 해줌
   ​

Python Code