[백준 / BOJ] 9202 Boggle

문제

출처 : www.acmicpc.net/problem/9202

9202번: Boggle

각칸에 알파벳 대문자가 적혀있는 보드가 주어졌을때 단어를 찾는 게임을 하려고한다.

 

w개의 찾을 단어가 주어지고, 각 칸마다 알파벳 대문자가 적혀있는 b개의 4*4 보드가 주어졌을때, 가장 많이 얻는 점수 , 가장 긴 문자열, 가장 많이 찾을수있는 단어의 수 를 구하는 문제다.

 

(이동은 현재위치에서 8방향(가로, 세로, 대각선)으로 갈수있다.)

 

풀이

일반적인 완탐만 사용할경우, 최악의 경우 (w = 300,000, b = 29) 일때, 

1. 보드의 모든 경우를 탐색하는 경우의수 = 29 *(4^12 + 8^4) = 약 5억

2. 찾을려는 단어가 만들어졌나 확인하는 경우의수 = (8 * 300,000)

이 나온다. 따라서,  보드에 도착했을때, 매번 탐색을 한다고 가정하면, 1번 * 2번 = (8 * 300,000) * 29 *(4^12 + 8^4) 번 반복하기 때문에, 10초라도 시간초과가 난다. 

 

1번과정 혹은 2번과정의 탐색횟수를 줄여야하는데, 어떤 위치에서 시작할때, 최댓값이 나오는지 알수없으므로 2번을 줄이는건 힘들다 생각해서 1번과정을 줄여줬다.

 

Trie알고리즘을 사용해서 탐색시간을 줄였는데, 

입력받은 단어들을 Trie구조로 만들어놓으면 2번 과정을 아예 없앨수있어서 약 5억번 반복으로 통과가능하다. (탐색과 동시에 단어 체크 가능)

 

로직은

1. 입력받은 단어를 Trie구조로 만들어놓는다.

ex) A, AB, ABC를 입력받으면

A

- B

- - C

형태로 저장해놓음

 

2. 보드의 각 칸을 기준으로 깊이우선탐색을 수행한다.

- 이때, NULL값을 참조하지않도록 보드의 알파벳이 단어의 알파벳과 같을때만 탐색해줬다.

- 만드는 경로가 여러가지 있을수있기 때문에, 백트래킹을 이용해 구현해줘야한다.

 

3. 탐색할때, 단어를 만들면서 탐색해준다(중복을 체크해주기위해). 이때, 현재 보고있는 주소의 end값이 true라면, (단어의 끝이라면, 중복된 단어인지 확인하고, 점수, 문자열, 찾은 단어의 수 를 업데이트 해준다.

- 중복 체크는 map자료구조를 사용했는데,. 모든 단어들을 map에 넣고, map["단어"] = false라면, 중복되지않은것, 아니라면 중복인것으로 판단해줬다.

 

푸는데 오래걸린 문제다.

(계속 틀렸습니다 나오는데, 반례를 못찾았음)

 

혹시 계속 틀렸습니다가 나온다면 아래 반례들을 확인해보자 (나한테 해당한 반례들이다)

 

1. 사전순으로 가장 앞서는 단어를 못 찾는경우 (내가 이걸 못찾아서 계속 틀렸었음...)

2

ABC
CBA

 

1

ABCX
XXXX
XXXX
XXXX

 

출력 : 

2 ABC 2

 

2. Trie 자료 구조를 잘못만든경우 

- (구현을 잘못만든경우 Trie구조에 ABC가 먼저 들어가서, AB와 A가 저장이 안될수도있다. 이때 잘못된 출력은 1 ABC 1 이 나올것이다.)

3

ABC
AB
A

 

1

ABCX
XXXX
XXXX
XXXX

 

출력 : 

1 ABC 3

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/9202%20Boggle/main.cpp

devxb/JJUNalgo