[BOJ][Python] 백준 1987번 - 알파벳

문제 링크: https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

 

---

문제 풀이

처음에 BFS로 풀려다가 안되겠다 싶어서 DFS로 변경했다. 어짜피 BFS로 풀진 못한다.

원래는 DFS를 재귀로 돌려서 풀려했지만 시간 초과가 나서 재귀를 최대한 적게 하는 방향으로 갔다. 먼저 4방향으로 갈 x, y의 좌표를 만들어주고, 알파벳이 중복되는지 알기 위해 set()을 썼다. in을 써도 O(1)이라서 시간 단축에 도움이 된다.

 

반복문을 돌려서 4방향으로 갈때 범위 안이고 알파벳이 중복되지 않는다면 set()에 (nx, ny)에 있는 알파벳을 넣어주고, 재귀로 count를 +1해주고 다시 DFS를 돌린다. 그리고 다시 set()에서 없애는 방법이 중요하다. 혹여나 최대 칸 수가 아닌 경우 돌아가기 위해서이다. 이 과정에서 백트래킹 과정이다. 아무튼 count를 최댓값으로 갱신해서 마지막에 출력하면 된다.

 

python으로 돌리면 시간 초과, pypy로 돌리면 메모리 초과가 떠서 최적화하는 과정에서 재귀를 적게 쓰고 혹여나 재귀 깊이 때문에 런타임 에러가 뜰거 같아서 sys.setrecursionlimit(10**9)를 해줬는데 없애니 정답을 맞췄다.

 

 

코드