목록9202 (1)

개발 쥬스

[백준/Java] 9202 Boggle

🔗 문제 링크: https://www.acmicpc.net/problem/9202 🔍 해결 과정이 문제를 간단히 요약하자면 최대 30만 값을 가진 w개의 단어 사전들이 존재하는데 최대 29번의 boggle을 진행해서 각 경우마다 단어사전에 해당하는 단어들을 찾은 다음 문제의 요구에 맞게 정답을 출력하면 되는 문제입니다. w의 최댓값이 30만이라는 점에서 시간복잡도를 최적화해야겠다는 생각이 들었지만, boggle 보드판의 크기는 4x4이고, 단어의 길이도 최대 8이라는 점을 감안했을 때 dfs와 가지치기(pruning)를 활용하여 백트래킹 기법을 사용해 시간 안에 문제를 해결할 수 있습니다. (참고로 문제에서 요구하는 최대 시간은 10초입니다.) 또한 단어 사전에 들어있는 단어의 개수가 최대 30만개이..
알고리즘 2024. 12. 11. 17:02
이전 Prev 1 Next 다음