[알고스팟] BOGGLE - 보글 게임 (C++)

문제

www.algospot.com/judge/problem/read/BOGGLE

algospot.com :: BOGGLE

풀이

 알고리즘 문제 해결 전략 서적에서 무식하게 풀기(Burute Force) 장에서 가장 처음 나오는 문제이다. 이 문제의 정답 비율이 극악인 이유는 단순히 모든 경우의 수를 확인하는 방법으로는 시간제한을 초과하기 때문이다. 따라서 BF장에서 나오는 문제이지만 동적 계획법(Dynamic programming)을 사용해야 시간 안에 통과할 수 있다.

 

 책을 처음 접했을 때는 BF방식으로 아무리 풀어보아도 시간초과만 나와서 좌절했던 기억이 있다... 이 문제는 동적 계획법을 모른다면 풀기 어려우니 너무 좌절하진 마시길!

 

시간이 초과되는 이유는 다음 예시와 같은 경우가 있기 때문이다.

 

아래와 같은 게임판에서 AAAAAAAAAB를 찾는다고 가정해 보자.

A	A	A	A	A
A	A	A	A	A
A	A	A	A	A
A	A	A	A	A
A	A	A	A	A

 

 모든 칸은 A이기 때문에 시작 지점은 어디든 될 수 있다. 하지만 단어의 마지막이 B임에도 게임판에는 존재하지 않기 때문에 모든 경우의 수를 따져보아도 최종적으로는 답이 나오지 않는다. 결국 해결하지 못하는 문제임에도 B를 찾기 전까지는 진행이 되므로 효율이 크게 떨어진다.

 

 예를 들어 A(0,0) ->A(1,1)->A(1,0)->A(1,1)->A(1,0)->...    처럼 위치가(0,0)인 위치에서 시작해 (1,1)과 (1,0)을 반복하는 경우와 A(1,0) ->A(1,1)->A(1,0)->A(1,1)->A(1,0)->...처럼 (1,0)에서 시작한 뒤 위와 같은 경로를 반복하는 경우는 시작 위치는 다르지만 결국 그 뒤의 경로는 모두 같다. 따라서 단순한 BF방식으로는 위처럼 같은 경로를 반복해서 계산하는 경우가 너무나 많다. 따라서 우리는 무의미한 반복을 막기 위해 동적 계획법을 사용해야 한다.

 

 동적 계획법에서는 반복되는 계산을 막기 위해 결과를 저장한다. 해당 문제는 펜으로 상하좌우와 대각의 인접한 칸으로 이동하며 영어 단어를 찾아내는 게임이다. 지나간 곳도 다시 지나가는 것이 가능하기 때문에 지나온 루트를 저장하는 것은 의미가 없다.

 예시의 경우처럼 두 번째 A를 찾기 위해 (1,1) 위치를 방문할 경우 최종적으로 답을 찾지 못 했다면, 두 번째로 (1,1)위치를 방문하는 것은 해답이 될 수 없다는 결과를 저장해 두면 무의미한 반복을 막을 수 있다. (더이상 두번째로 (1,1)의 방문을 막을 수 있음.)

즉, 우리는 찾는 단어의 n번째 글자를 해당 위치를 방문했지만 최종적으로 모든 글자를 찾지 못한다면, n번째 글자를 위해 그 위치를 방문하지 못하도록 설계해야 한다.

 

 따라서 모든 값을 true로 초기화한

bool posAlphabet[5][5][10]를 이용하여 [r][c]위치에 n번째 글자를 방문 가능 여부를 기록한다.

 

 나머지는 재귀함수를 통해 다음 이동 위치의 글자와 방문 가능 여부를 확인하여 재귀호출하고, 단어의 끝에 도달하면 성공 여부를 반환한다.

 

결과: 4ms

 

코드