문제는 아래 링크 참고
https://www.acmicpc.net/problem/9202
- 문제 요약
문제는 보드판에서 주어진 단어들을 찾는것이다. 단어 리스트는 주어지는데
좌우 대각선으로 글자를 조합해 단어를 만들수 있다.
2. 문제 해결 방법
문제 해결방법은 재귀를 이용한 완전 탐색을 생각해봤다.
글자가 1글자 남을때까지 계속 재귀적으로 좌우대각선을 탐색하게끔..
테스트 케이스는 통과 했으나 어떤 케이스에 Fail이 되는지 사실 잘 모르겠다.
채점 결과는 시간오버가 아니라 틀렸습니다. 이기 때문에 틀린 Test Case가 있는 것 같다.
틀린 Test Case를 알려주시는분에게는 소소한 상품을 드립니다^^;; 하하..
3. 소스 코드
엄청 헤맸는데.. 문제를 잘 못 읽어서 그런거 였어
일단 아래 부분을 한번 확인해봐 (나 같은 경우는 3번이 문제였어)
1. Boggle에서 찾을 단어를 여러번 등록 할 경우 (Ex. ACM 등록 후 또 ACM)
2. 길이가 3 미만인 경우에 개수를 세는지 (Ex. AL, OP, M)
3. 가장 길이가 긴 단어의 길이가 같을 때 사전순 정렬이 되어 있는지 (Ex. ICPC, GCPC)
if(wordlength >= maxlength) {
maxlength = wordlength;
if(maxString.compareTo(test.result_words.get(i).get(j)) > 0 ) {
maxString = test.result_words.get(i).get(j);
}
}
위의 경우에는 wordlength == maxlength 인경우에는 잘 동작하는데
wordlength > maxlength 경우에는 의도대로 동작이 안 될거 같아
A.CompareTo(B) 면 A > B : 1, A = B : 0, A < B : -1 이지 않아?
(test.result_words.get(i).get(j) 요약해서 wordString)
위에 따르면 maxString > wordString 이면 maxString이 더 긴 건데
maxString 을 갱신해 줄 필요가 없는 거 같아
참고 소스 코드: 9202_Boggle.cpp
아하 오키 무슨말인지 이해했음. 아래 if문은 사전순으로 정렬하기 위한것이었는데 maxString이 더 클경우는 그럴 필요가 없구나!!
ㅇㅇ 맞는데.. 정확히 얘기하면 두 개로 나눠야 할 거 같아
같을 때는 지금 처럼 하면 되는데 (wordlength > maxlength) 일 경우에는
maxString.compareTo(test.result_words.get(i).get(j)) < 0 일 때 maxString을 갱신해 줘야 하는 거지